Space Complexity 空間複雜度 - paulip114/blog GitHub Wiki

🧠 空間複雜度是什麼?

空間複雜度是指你的程式在執行時額外使用了多少記憶體,通常用 Big-O 表示,例如:O(1)、O(n)、O(n²)...


✅ 分析空間複雜度的步驟:

1️⃣ 看你有沒有用 額外的資料結構

  • 用了新的陣列?hash map?stack?queue?
  • 這些的大小是不是跟輸入有關?

範例:

let arr = [1, 2, 3, 4];      // 輸入 O(n)
let result = [];             // 額外空間:O(n)
for (let i = 0; i < arr.length; i++) {
  result.push(arr[i] * 2);
}

➡ 空間複雜度:O(n)(因為創了一個跟輸入等長的新陣列)


2️⃣ 常數級空間是 O(1)

如果你只用幾個變數(例如計數器、指標),不管輸入多大,都只占固定空間,就是 O(1)

範例:

let sum = 0;
for (let i = 0; i < arr.length; i++) {
  sum += arr[i];
}

➡ 空間複雜度:O(1)


3️⃣ 遞迴(recursion)要算 stack 空間

每一次遞迴呼叫會佔用一層 call stack,因此要把這個加進空間複雜度裡。

範例:

function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

➡ 遞迴深度是 n → 空間複雜度是 O(n)(因為 call stack 有 n 層)


4️⃣ In-place 操作不需要額外空間 → O(1)

像是:

  • 原地反轉陣列
  • 用 two pointers 替換元素

這些都不會開新空間 → 空間複雜度是 O(1)


🧪 小技巧:和時間複雜度相比

  • 時間複雜度:看你「跑幾次」
  • 空間複雜度:看你「開了多少空間」

💡 範例對照整理

程式 空間複雜度說明 空間複雜度
僅用變數統計總和 無新結構 O(1)
建立新陣列儲存結果 陣列長度為 n O(n)
遞迴樹遍歷 stack 深度為 h O(h)
雙指針交換元素(原地) 沒有新資料結構 O(1)