[Python]空間複雜度（Space Complexity）

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

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

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

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

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

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

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

print(sum_two_numbers(5, 10))

✅ 分析：不管 a 和 b 的值多大，程式只使用一個變數 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 陣列），總共需要 n² 個空間，因此空間複雜度是 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

總結

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

通常：

• 如果我們 希望節省時間，可能會使用額外的空間（例如快取、動態規劃）。
• 如果我們 希望節省空間，可能會 重複計算，但會花費更多時間。