[Python]空間複雜度(Space Complexity)

[Python]空間複雜度(Space Complexity)

更新於 發佈於 閱讀時間約 5 分鐘

讓我們從 空間複雜度(Space Complexity) 的基本概念開始,並搭配 Python 程式 來幫助理解。


1️⃣ 什麼是空間複雜度?

空間複雜度指的是 演算法在運行時所需的記憶體量,通常用 大O符號(Big-O notation) 來表示,例如:

  • O(1) → 只使用固定的額外空間(常數空間)
  • O(n) → 需要與輸入大小成正比的空間
  • O(n²) → 需要平方級別的空間

2️⃣ Python 範例:不同空間複雜度的程式

我們用 Python 來示範 不同的空間複雜度,從 O(1) 到 O(n)

(1) O(1) 空間複雜度:只使用固定變數

def sum_two_numbers(a, b):
result = a + b # 只使用了一個變數 (result),所以是 O(1)
return result

print(sum_two_numbers(5, 10))

分析:不管 ab 的值多大,程式只使用一個變數 result,所以空間複雜度是 O(1)


(2) O(n) 空間複雜度:建立一個新列表

def create_list(n):
lst = [] # 需要額外的空間來存儲 n 個元素
for i in range(n):
lst.append(i)
return lst

print(create_list(5)) # [0, 1, 2, 3, 4]

分析

這個函式建立了一個長度為 n 的列表 lst,需要額外的記憶體來存放 n 個數字,所以空間複雜度是 O(n)


(3) O(n²) 空間複雜度:建立一個 2D 矩陣

def create_matrix(n):
matrix = [[0] * n for _ in range(n)] # 創建一個 n×n 的二維陣列
return matrix

print(create_matrix(3))

分析

這裡建立了一個 n x n 的矩陣(2D 陣列),總共需要 個空間,因此空間複雜度是 O(n²)


3️⃣ 空間優化技巧

當你寫程式時,如何降低空間複雜度呢?這裡有幾種技巧:

1. 原地修改(In-place Modification)

  • 避免創建新變數,直接修改原始輸入資料
  • 範例:反轉列表(O(n) → O(1))
    def reverse_list_inplace(lst):
    left, right = 0, len(lst) - 1
    while left < right:
    lst[left], lst[right] = lst[right], lst[left] # 交換元素
    left += 1
    right -= 1
    return lst

    print(reverse_list_inplace([1, 2, 3, 4, 5])) # [5, 4, 3, 2, 1]

2. 使用迭代代替遞歸

  • 遞歸通常會佔用大量的函式呼叫堆疊(stack),導致 O(n) 或 O(n²) 空間
  • 範例:費波那契數列(遞歸 → 迭代,降低空間)
    def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
    a, b = b, a + b # 只使用兩個變數 (O(1))
    return a

    print(fibonacci(10)) # 55

總結

raw-image

時間複雜度(Time Complexity)空間複雜度(Space Complexity) 是兩個非常相關的概念,因為演算法在執行時,通常需要在「時間」和「空間」之間做取捨(trade-off)。


raw-image

通常:

  • 如果我們 希望節省時間,可能會使用額外的空間(例如快取動態規劃)。
  • 如果我們 希望節省空間,可能會 重複計算,但會花費更多時間。
avatar-img
螃蟹_crab的沙龍
137會員
243內容數
本業是影像辨識軟體開發,閒暇時間進修AI相關內容,將學習到的內容寫成文章分享。
留言
avatar-img
留言分享你的想法!
螃蟹_crab的沙龍 的其他內容
什麼是時間複雜度? 時間複雜度(Time Complexity)是用來衡量演算法執行時間隨著輸入大小變化的增長速度。通常使用 Big-O 表示法(O 記號)來描述,目的是估算最壞情況下的運行時間。 時間複雜度的計算主要基於以下幾個原則: 忽略常數係數:O(2n) 與 O(n) 視為相同,因為增
什麼是時間複雜度? 時間複雜度(Time Complexity)是用來衡量演算法執行時間隨著輸入大小變化的增長速度。通常使用 Big-O 表示法(O 記號)來描述,目的是估算最壞情況下的運行時間。 時間複雜度的計算主要基於以下幾個原則: 忽略常數係數:O(2n) 與 O(n) 視為相同,因為增