演算法基礎：空間複雜度完全指南
深入理解程式的記憶體使用與優化策略
目錄
什麼是空間複雜度？
空間複雜度（Space Complexity）描述了演算法執行時所需的記憶體空間如何隨著輸入規模增長。它回答了一個關鍵問題：「當資料量變大時，程式需要多少記憶體？」
為什麼空間複雜度很重要？
# 情境：處理一個 10GB 的檔案
# 方法 1：全部載入記憶體（可能造成記憶體不足）
def process_file_v1(filename):
with open(filename, 'r') as f:
content = f.read() # 需要 10GB 記憶體！
return content.upper()
# 方法 2：逐行處理（記憶體使用量固定）
def process_file_v2(filename):
result = []
with open(filename, 'r') as f:
for line in f: # 一次只載入一行
result.append(line.upper())
return ''.join(result)
# 方法 3：串流處理（最省記憶體）
def process_file_v3(filename, output_filename):
with open(filename, 'r') as f_in, open(output_filename, 'w') as f_out:
for line in f_in:
f_out.write(line.upper())空間複雜度的組成
1. 輸入空間
演算法輸入資料佔用的空間（通常不計入額外空間）。
2. 輔助空間（Auxiliary Space）
演算法執行過程中額外使用的空間。
def example_spaces(arr):
n = len(arr) # 輸入空間：O(n)
# 輔助空間
temp_list = [0] * n # O(n) 額外空間
counter = 0 # O(1) 額外空間
result_dict = {} # O(k) 額外空間，k 是不同元素數量
return result_dict常見的空間複雜度
O(1) - 常數空間
無論輸入多大，使用的額外空間都固定。
def find_max_in_place(arr):
"""原地找最大值 - O(1) 空間"""
if not arr:
return None
max_val = arr[0] # 只用一個變數
for num in arr:
if num > max_val:
max_val = num
return max_val
def swap_elements(arr, i, j):
"""原地交換 - O(1) 空間"""
arr[i], arr[j] = arr[j], arr[i]
return arr
def reverse_array_in_place(arr):
"""原地反轉陣列 - O(1) 空間"""
left, right = 0, len(arr) - 1
while left < right:
arr[left], arr[right] = arr[right], arr[left]
left += 1
right -= 1
return arrO(n) - 線性空間
空間使用與輸入成正比。
def create_copy(arr):
"""建立副本 - O(n) 空間"""
return arr.copy() # 需要 n 個元素的空間
def array_to_dict(arr):
"""陣列轉字典 - O(n) 空間"""
result = {}
for i, val in enumerate(arr):
result[i] = val
return result
def get_unique_elements(arr):
"""取得唯一元素 - O(n) 空間（最壞情況）"""
return list(set(arr)) # set 需要額外空間
def build_frequency_map(arr):
"""建立頻率表 - O(k) 空間，k <= n"""
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
return freqO(n²) - 平方空間
通常出現在二維資料結構。
def create_matrix(n):
"""建立 n×n 矩陣 - O(n²) 空間"""
matrix = []
for i in range(n):
row = []
for j in range(n):
row.append(0)
matrix.append(row)
return matrix
def adjacency_matrix(edges, n):
"""建立鄰接矩陣 - O(n²) 空間"""
matrix = [[False] * n for _ in range(n)]
for u, v in edges:
matrix[u][v] = True
matrix[v][u] = True # 無向圖
return matrix
def all_pairs_distances(points):
"""計算所有點對距離 - O(n²) 空間"""
n = len(points)
distances = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
if i != j:
distances[i][j] = calculate_distance(points[i], points[j])
return distances遞迴與空間複雜度
理解調用堆疊
def factorial_recursive(n):
"""
遞迴計算階乘
空間複雜度：O(n) - 調用堆疊深度
"""
if n <= 1:
return 1
return n * factorial_recursive(n - 1)
# 調用堆疊視覺化：
# factorial_recursive(5)
# ├─ 5 * factorial_recursive(4)
# │ ├─ 4 * factorial_recursive(3)
# │ │ ├─ 3 * factorial_recursive(2)
# │ │ │ ├─ 2 * factorial_recursive(1)
# │ │ │ │ └─ return 1
# │ │ │ └─ return 2
# │ │ └─ return 6
# │ └─ return 24
# └─ return 120尾遞迴優化（Python 不支援，但概念重要）
def factorial_tail_recursive(n, accumulator=1):
"""
尾遞迴版本（理論上可優化為 O(1) 空間）
但 Python 不進行尾遞迴優化
"""
if n <= 1:
return accumulator
return factorial_tail_recursive(n - 1, n * accumulator)
def factorial_iterative(n):
"""
迭代版本 - O(1) 空間
"""
result = 1
for i in range(1, n + 1):
result *= i
return result樹遞迴的空間分析
def fibonacci_recursive(n):
"""
樹狀遞迴
時間：O(2ⁿ)
空間：O(n) - 最大調用深度
"""
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
def fibonacci_memoized(n, memo=None):
"""
記憶化遞迴
時間：O(n)
空間：O(n) - 調用堆疊 + 記憶化表
"""
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memoized(n - 1, memo) + fibonacci_memoized(n - 2, memo)
return memo[n]空間優化技巧
技巧 1：滾動陣列
# 原始版本：O(n) 空間
def fibonacci_dp_v1(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0], dp[1] = 0, 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 優化版本：O(1) 空間
def fibonacci_dp_v2(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for i in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1技巧 2：位元操作節省空間
# 使用布林陣列：每個元素 1 byte
def sieve_normal(n):
is_prime = [True] * (n + 1) # O(n) bytes
# ... 篩法邏輯
return is_prime
# 使用位元陣列：每個元素 1 bit
def sieve_bitarray(n):
# 每個整數可存 32 個布林值
size = (n + 31) // 32
is_prime = [0xFFFFFFFF] * size # O(n/32) bytes
def set_composite(num):
is_prime[num // 32] &= ~(1 << (num % 32))
def is_prime_number(num):
return bool(is_prime[num // 32] & (1 << (num % 32)))
# ... 篩法邏輯
return is_prime技巧 3：生成器節省記憶體
# 一次性建立所有結果：O(n) 空間
def get_squares_list(n):
return [i ** 2 for i in range(n)]
# 使用生成器：O(1) 空間
def get_squares_generator(n):
for i in range(n):
yield i ** 2
# 使用範例
# 列表版本
squares_list = get_squares_list(1000000) # 佔用大量記憶體
for square in squares_list:
process(square)
# 生成器版本
for square in get_squares_generator(1000000): # 幾乎不佔記憶體
process(square)技巧 4：原地演算法
# 非原地排序：O(n) 額外空間
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # 建立新陣列
right = merge_sort(arr[mid:])
return merge(left, right)
# 原地排序：O(1) 額外空間
def bubble_sort_in_place(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 原地分割（用於快速排序）
def partition_in_place(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1實戰分析：記憶體使用測量
import sys
import tracemalloc
def measure_memory(func, *args):
"""測量函數的記憶體使用"""
tracemalloc.start()
# 執行前的記憶體
before = tracemalloc.get_traced_memory()[0]
# 執行函數
result = func(*args)
# 執行後的記憶體
after = tracemalloc.get_traced_memory()[0]
tracemalloc.stop()
# 計算差異
memory_used = after - before
return memory_used, result
# 測試不同資料結構的記憶體使用
def test_list(n):
return [i for i in range(n)]
def test_set(n):
return {i for i in range(n)}
def test_dict(n):
return {i: i for i in range(n)}
# 測量 Python 物件大小
n = 1000
print(f"List 大小: {sys.getsizeof(test_list(n))} bytes")
print(f"Set 大小: {sys.getsizeof(test_set(n))} bytes")
print(f"Dict 大小: {sys.getsizeof(test_dict(n))} bytes")
# 深入分析記憶體使用
def analyze_memory_growth():
sizes = [100, 1000, 10000, 100000]
for size in sizes:
# 測試列表
mem_list, _ = measure_memory(test_list, size)
# 測試字典
mem_dict, _ = measure_memory(test_dict, size)
print(f"n={size}:")
print(f" List: {mem_list:,} bytes")
print(f" Dict: {mem_dict:,} bytes")常見的空間複雜度陷阱
陷阱 1：字串的不可變性
# 低效版本：O(n²) 空間
def build_string_inefficient(n):
result = ""
for i in range(n):
result += str(i) # 每次都建立新字串！
return result
# 高效版本：O(n) 空間
def build_string_efficient(n):
parts = []
for i in range(n):
parts.append(str(i))
return "".join(parts)陷阱 2：切片操作
# 切片會建立新陣列
def process_subarray_v1(arr, start, end):
subarray = arr[start:end] # O(end - start) 額外空間
return sum(subarray)
# 避免切片，直接處理
def process_subarray_v2(arr, start, end):
total = 0
for i in range(start, end): # O(1) 額外空間
total += arr[i]
return total陷阱 3：隱藏的空間使用
# sorted() 建立新列表
def find_kth_largest_v1(arr, k):
sorted_arr = sorted(arr, reverse=True) # O(n) 額外空間
return sorted_arr[k - 1]
# 使用堆，空間更優
import heapq
def find_kth_largest_v2(arr, k):
heap = []
for num in arr:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap) # 維持 k 個元素，O(k) 空間
return heap[0]空間與時間的權衡
範例 1：兩數之和
# 方法 1：暴力法 - 時間 O(n²)，空間 O(1)
def two_sum_brute_force(nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
# 方法 2：雜湊表 - 時間 O(n)，空間 O(n)
def two_sum_hash(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []範例 2：檢查重複
# 方法 1：排序 - 時間 O(n log n)，空間 O(1)（原地排序）
def has_duplicate_sort(nums):
nums.sort() # 原地排序
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return False
# 方法 2：集合 - 時間 O(n)，空間 O(n)
def has_duplicate_set(nums):
return len(nums) != len(set(nums))記憶體優化最佳實踐
1. 選擇合適的資料結構
# 根據需求選擇資料結構
# 需要快速查找？用 dict/set
# 需要保持順序？用 list
# 需要節省空間？考慮 array.array 或 numpy
import array
# Python list：每個整數約 28 bytes
py_list = [i for i in range(1000)]
# array.array：每個整數 4 bytes
arr = array.array('i', range(1000))
# 空間差異顯著！2. 及時釋放記憶體
def process_large_data():
# 處理大型資料
huge_data = load_huge_file()
result = process(huge_data)
# 明確刪除不再需要的大型物件
del huge_data
# 如果需要，強制垃圾回收
import gc
gc.collect()
return result3. 使用記憶體映射檔案
import mmap
def process_huge_file(filename):
"""使用記憶體映射處理超大檔案"""
with open(filename, 'r+b') as f:
with mmap.mmap(f.fileno(), 0) as mmapped_file:
# 可以像處理字串一樣處理檔案
# 但不會全部載入記憶體
for line in iter(mmapped_file.readline, b""):
process_line(line)總結
空間複雜度分析是寫出記憶體高效程式的關鍵。記住這些要點：
- 了解你的資料規模：1MB 還是 1GB？這決定了優化策略
- 權衡是必要的：時間換空間，或空間換時間
- 遞迴要小心：調用堆疊也佔記憶體
- 原地演算法很強大：但可能犧牲可讀性
- 測量實際使用：理論分析後要實測驗證
記憶體優化不只是技術問題，更是一種思維方式。在資源受限的環境中（如嵌入式系統或處理大資料），空間複雜度往往比時間複雜度更重要。
練習題
- 實現一個原地反轉鏈結串列的演算法
- 設計一個 O(1) 空間的找出陣列中缺失數字的方法
- 優化遞迴演算法，減少調用堆疊深度
- 比較不同資料結構在相同任務下的記憶體使用