複雜度分析練習題

面試方法論值得會更新於 Oct 9, 2026

範圍 — 20 道自我測驗題 — 讀程式片段、說出複雜度、再對答案檢查自己。另見 — complexity_cheatsheet.md — 參考用的對照表；time_space_complexity.md — 完整的推導過程。

練習從程式片段判斷時間複雜度與空間複雜度。 Google 面試官非常愛追問這一塊——預期會有後續問題，例如「還能更快嗎？」以及「如果最佳化的話空間是多少？」

使用方式

讀完程式片段
在看答案之前先自己判斷時間與空間複雜度
對照解說檢查你的推理
把答錯的題目標上星號（⭐）——之後回來重做

想要被評分而不是自己改？網站上的 Complexity Quiz 會從這個 repo 隨機抽出 Python 程式片段，讓你輸入時間與空間複雜度的答案並逐題評分 — 最後還附上依主題分類的統計。

練習 1：巢狀迴圈

java

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // O(1) work
    }
}

答案

時間：O(N²) 內層迴圈執行次數：N + (N-1) + (N-2) + … + 1 = N(N+1)/2 → O(N²)

空間：O(1)

常見錯誤：因為「j 從 i 開始」就說是 O(N)。這個級數的總和仍然是平方級。

練習 2：以乘法遞增的迴圈

java

int i = 1;
while (i < n) {
    // O(1) work
    i *= 2;
}

答案

時間：O(log N) i 依序取 1、2、4、8、…，直到 i ≥ N。也就是 log₂(N) 次迭代。

空間：O(1)

練習 3：以除法遞減的迴圈

java

for (int i = n; i >= 1; i /= 2) {
    for (int j = 0; j < i; j++) {
        // O(1) work
    }
}

答案

時間：O(N) 內層迴圈執行次數：N + N/2 + N/4 + … + 1 = 2N → O(N)（等比級數！）

空間：O(1)

常見錯誤：說成 O(N log N)。每次迭代的工作量都減半——等比級數收斂到 2N。

練習 4：遞迴費氏數列（樸素版）

python

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

答案

時間：O(2^N) — 更精確地說是 O(φ^N)，其中 φ ≈ 1.618（黃金比例）每次呼叫都分岔成 2 個子呼叫。這棵樹約有 2^N 個節點。

空間：O(N) — 遞迴堆疊深度為 N（會一路沿著最左的分支下去，之後才回傳）

常見錯誤：說空間是 O(2^N)。堆疊在任一時刻只裝著一條路徑。

練習 5：迴圈中的 HashMap

java

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
    map.put(nums[i], i);
}
for (int i = 0; i < n; i++) {
    int complement = target - nums[i];
    if (map.containsKey(complement)) return true;
}

答案

時間：O(N) 平均 — HashMap 的 put/get 是攤還 O(1) 空間：O(N) — 最多存 N 筆資料

注意：如果所有 key 都雜湊到同一個 bucket，最壞情況是 O(N²)。面試時可以提一下，但主要陳述平均情況。

練習 6：排序 + 二分搜尋

python

nums.sort()  # Timsort
for x in nums:
    idx = bisect_left(nums, target - x)

答案

時間：O(N log N) — 排序是 O(N log N)，迴圈是 N × O(log N) = O(N log N)。總計：O(N log N)。

空間：Timsort（Python）為 O(N)，原地排序（quicksort）則為 O(log N)

練習 7：格子上的 BFS

python

from collections import deque
queue = deque([(0, 0)])
visited = set()
visited.add((0, 0))
while queue:
    r, c = queue.popleft()
    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
        nr, nc = r+dr, c+dc
        if 0 <= nr < m and 0 <= nc < n and (nr,nc) not in visited:
            visited.add((nr, nc))
            queue.append((nr, nc))

答案

時間：O(M·N) — 每一格最多被拜訪一次 空間：O(M·N) — visited 集合 + 佇列最多可裝 M·N 格

常見錯誤：因為有 4 個方向就說成 O(M·N·4)。那個 4 是常數——要省略。

練習 8：合併排序

python

def mergeSort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)  # merge is O(N)

答案

時間：O(N log N) — 共 log N 層，每一層合併的總工作量為 O(N)

空間：O(N) — 合併時會建立新陣列；遞迴堆疊是 O(log N)，但被合併陣列的 O(N) 蓋過去

注意：arr[:mid] 會複製一份——這就是那個 O(N) 空間。原地合併排序只要 O(log N) 空間，但實作困難得多。

練習 9：產生所有子集合

python

def subsets(nums):
    result = [[]]
    for num in nums:
        result += [curr + [num] for curr in result]
    return result

答案

時間：O(N × 2^N) — 共 2^N 個子集合，每個最長 N，複製都要成本

空間：O(N × 2^N) — 要存下所有子集合

逐步分析：處理完 k 個元素後，result 中有 2^k 個子集合。我們複製全部並加入 num → 2^k 份平均長度 k/2 的複本。

練習 10：滑動視窗

python

left = 0
max_len = 0
freq = {}
for right in range(len(s)):
    freq[s[right]] = freq.get(s[right], 0) + 1
    while len(freq) > k:
        freq[s[left]] -= 1
        if freq[s[left]] == 0: del freq[s[left]]
        left += 1
    max_len = max(max_len, right - left + 1)

答案

時間：O(N) — left 指標只會往前走，總移動次數 ≤ N。每個字元最多進出視窗各一次。

空間：O(K) 或 O(min(N, Σ))，其中 Σ = 字母集大小

常見錯誤：因為 for 迴圈裡有 while 迴圈就說是 O(N²)。但 left 永遠不會往回走——攤還後是 O(N)。

練習 11：帶路徑壓縮 + 按秩合併的併查集

java

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);  // path compression
    return parent[x];
}
void union(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (rank[px] < rank[py]) parent[px] = py;
    else if (rank[px] > rank[py]) parent[py] = px;
    else { parent[py] = px; rank[px]++; }
}

答案

時間：每次操作 O(α(N)) — α 是反 Ackermann 函數，對所有實務上的輸入而言等同 O(1)（當 N ≤ 2^65536 時 α(N) ≤ 5）

空間：O(N) — parent 與 rank 陣列

關鍵洞見：只做路徑壓縮是攤還 O(log N)。只做按秩合併也是 O(log N)。兩者合用：O(α(N)) ≈ O(1)。

練習 12：字典樹的插入與搜尋

java

void insert(String word) {
    TrieNode node = root;
    for (char c : word.toCharArray()) {
        if (node.children[c - 'a'] == null)
            node.children[c - 'a'] = new TrieNode();
        node = node.children[c - 'a'];
    }
    node.isEnd = true;
}

答案

時間：O(M)，其中 M = 單字長度

空間：最壞情況 O(M)（沒有共用前綴時的新節點數）

N 個平均長度 M 的單字，整棵字典樹最壞情況是 O(26 × M × N)，但因為前綴共用，實際上通常小很多。

練習 13：堆積(heap) — 最近的 K 個點

python

import heapq
def kClosest(points, k):
    return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)

答案

時間：O(N log K) — nsmallest 維護一個大小為 K 的 max-heap，處理全部 N 個點

空間：O(K) — 堆積(heap) 本身

替代做法：QuickSelect 平均 O(N) 時間、O(1) 額外空間（但會改動輸入）。

練習 14：使用二維表格的 DP

java

// LC 72 — Edit Distance
int[][] dp = new int[m + 1][n + 1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
    for (int j = 1; j <= n; j++) {
        if (word1.charAt(i-1) == word2.charAt(j-1))
            dp[i][j] = dp[i-1][j-1];
        else
            dp[i][j] = 1 + Math.min(dp[i-1][j-1],
                            Math.min(dp[i-1][j], dp[i][j-1]));
    }
}

答案

時間：O(M·N) — 填滿 M×N 的表格，每格 O(1)

空間：O(M·N) — 但可用滾動陣列最佳化到 O(min(M,N))（只需要前一列）

後續追問：「空間可以再省嗎？」→ 用大小為 min(M,N)+1 的一維陣列，並用一個暫存變數保存對角線值來原地更新。

練習 15：回溯 — N 皇后

python

def solveNQueens(n):
    def backtrack(row, cols, diags, anti_diags):
        if row == n:
            result.append(board_snapshot())
            return
        for col in range(n):
            if col in cols or (row-col) in diags or (row+col) in anti_diags:
                continue
            # place queen and recurse
            backtrack(row+1, cols|{col}, diags|{row-col}, anti_diags|{row+col})

答案

時間：O(N!) — 第 0 列有 N 種選擇、第 1 列約 N-1、第 2 列約 N-2，依此類推（有剪枝的話實務上少得多）

空間：O(N) — 遞迴深度為 N，每個集合最多裝 N 個元素

注意：解的數量成長速度遠低於 N!。當 N=8 時，8! = 40320 種擺法中只有 92 組解。

練習 16：攤還分析 — 動態陣列

java

ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < n; i++) {
    list.add(i);  // occasionally triggers resize and copy
}

答案

時間：總共 O(N)，每次 add 攤還 O(1)

擴容發生在大小為 1、2、4、8、…、N 的時候。總複製次數：1 + 2 + 4 + … + N = 2N → O(N)。

空間：O(N)

關鍵洞見：即使單次 add 可能是 O(N)（擴容當下），攤還成本仍是 O(1)，因為擴容以指數方式變得稀少。

練習 17：在迴圈中串接字串

java

String result = "";
for (int i = 0; i < n; i++) {
    result += chars[i];  // creates new String each time
}

答案

時間：O(N²) — 每次串接都會複製整個既有字串。複製量：1 + 2 + 3 + … + N = O(N²)

空間：O(N) — 結果字串（中間產生的字串會被 GC 回收）

修正方式：改用 StringBuilder，總時間變 O(N)。

這是經典的面試陷阱。在 Java 中一定要提到 StringBuilder/StringBuffer。

練習 18：雙指標 — Container with Most Water

python

left, right = 0, len(height) - 1
max_area = 0
while left < right:
    max_area = max(max_area, min(height[left], height[right]) * (right - left))
    if height[left] < height[right]:
        left += 1
    else:
        right -= 1

答案

時間：O(N) — 每次迭代移動一個指標，總共最多 N 次迭代

空間：O(1)

為什麼可行：移動較矮的那一側是唯一可能增加面積的做法（移動較高的一側只會縮小寬度，而高度不會增加）。

練習 19：樹的 DFS 加上序列化

python

def serialize(root):
    if not root: return "null"
    return str(root.val) + "," + serialize(root.left) + "," + serialize(root.right)

答案

時間：O(N²) — 在字串串接會產生複本的語言中（Python、Java String）。每次串接都會複製愈來愈長的字串。

空間：O(N) — 遞迴堆疊（若樹平衡：O(log N) 堆疊 + O(N) 結果字串）

修正方式：用 list 收集、最後再 join → O(N) 時間。

python

def serialize(root):
    parts = []
    def dfs(node):
        if not node: parts.append("null"); return
        parts.append(str(node.val))
        dfs(node.left)
        dfs(node.right)
    dfs(root)
    return ",".join(parts)  # O(N) total

練習 20：搭配優先佇列的 Dijkstra

java

PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);
pq.offer(new int[]{src, 0});
int[] dist = new int[V];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;

while (!pq.isEmpty()) {
    int[] curr = pq.poll();
    int u = curr[0], d = curr[1];
    if (d > dist[u]) continue;  // skip outdated entries
    for (int[] edge : graph[u]) {
        int v = edge[0], w = edge[1];
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.offer(new int[]{v, dist[v]});
        }
    }
}

答案

時間：O((V + E) log V) — 每個頂點只會被真正取出一次（靠跳過檢查），每條邊只鬆弛一次，堆積(heap) 操作為 O(log V)。堆積(heap) 中最多可能有 E 筆資料 → 嚴格說是 O((V + E) log E) = O((V + E) log V)，因為 log E ≤ log V² = 2 log V。

空間：O(V + E) — dist 陣列 O(V)，堆積(heap) 最多裝 O(E) 筆

注意：如果少了 if (d > dist[u]) continue 這個檢查，就會處理到過期的資料，可能變成 O(E log E) 且常數更差。

為自己評分

分數	程度	下一步
答對 18-20 題	已達 Google 水準	專注在速度——30 秒內講清楚
答對 14-17 題	就差一點	複習 complexity_cheatsheet.md 中的數學直覺
答對 10-13 題	還需加強	研讀等比級數、攤還分析、遞迴樹
答對 < 10 題	基礎不足	從 Big-O 基礎開始，用簡單例子練習