讓我們從 空間複雜度（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))
✅ 分析：不管 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）。
通常：
- 如果我們 希望節省時間，可能會使用額外的空間（例如快取、動態規劃）。
- 如果我們 希望節省空間，可能會 重複計算，但會花費更多時間。