Big O#

Big O 是描述演算法效率的語言與衡量標準。不徹底理解它，不僅可能在面試中被嚴格評判，更難以判斷自己的演算法是否越來越快或越來越慢。務必掌握這個概念。

An Analogy（類比）#

想像你有一個很大的檔案在硬碟裡，需要盡快傳給遠在美國另一端的朋友。你應該怎麼傳？

大多數人第一個想法是 email 或 FTP 電子傳輸。這個想法合理，但只對了一半：

• 電子傳輸：時間與檔案大小成正比，記為 O(s)，s 為檔案大小
• 實體搭飛機傳送：不論檔案多大，到達時間固定，記為 O(1)

當檔案非常大（例如 1 TB）時，搭飛機可能反而更快。這就是 漸進執行時間（asymptotic runtime） 的概念——我們描述的是時間如何隨輸入規模增長，而非精確的執行時間。

Time Complexity（時間複雜度）#

Big O、Big Theta、Big Omega#

學術界用三種符號描述執行時間：

• O（big O）：描述執行時間的上界。印出陣列所有值可以說是 O(N)，也可以說是 O(N²)（都是上界，但後者不夠精確）。
• Ω（big omega）：描述執行時間的下界。印出陣列所有值至少需要 Ω(N) 時間。
• Θ（big theta）：同時是上界與下界，即緊界。若一個演算法是 Θ(N)，表示它既是 O(N) 也是 Ω(N)。

在業界（也就是面試中），人們傾向將 Θ 和 O 合併使用。業界的 big O 更接近學術界的 big theta，即盡量給出最緊的執行時間描述。

Best Case、Worst Case、Expected Case#

以 Quick Sort 為例：

• Best Case（最佳情況）：所有元素相等，只需遍歷一次，O(N)
• Worst Case（最壞情況）：每次選到最大的 pivot，遞迴無法平均分割，退化為 O(N²)
• Expected Case（期望情況）：通常情況下，O(N log N)

Best/Worst/Expected Case 描述的是特定輸入或情境下的 big O 時間。Big O / Big Omega / Big Theta 描述的是執行時間的上界、下界和緊界。兩者沒有固定的對應關係，不要混淆。

Space Complexity（空間複雜度）#

演算法除了時間，也要考慮記憶體用量。空間複雜度是時間複雜度的平行概念。

• 建立大小 n 的陣列：O(n) 空間
• 建立 n×n 的二維陣列：O(n²) 空間
• 遞迴呼叫的 stack 空間也計入：n 層遞迴需要 O(n) 空間

注意：某函式被呼叫 O(n) 次，不代表就需要 O(n) 空間。如果這些呼叫不是同時存在於 call stack 上（例如迴圈呼叫），只需要 O(1) 額外空間。

Drop the Constants（捨棄常數）#

Big O 描述的是增長速率，而非精確時間。因此，常數可以省略：

• O(2N) 就是 O(N)
• 一個有兩個非巢狀 for 迴圈的演算法仍然是 O(N)，不是 O(2N)

若你要精確計算常數，就得深入到組合語言層級，考慮乘法比加法需要更多指令等問題——這樣做既繁瑣又不必要。接受 O(N) 不代表一定優於 O(N²)，Big O 只描述增長趨勢。

Drop the Non-Dominant Terms（捨棄非主導項）#

類似捨棄常數，也要捨棄非主導項：

• O(N² + N) → O(N²)
• O(N + log N) → O(N)
• O(5 × 2ᴺ + 1000N¹⁰⁰) → O(2ᴺ)

若有兩個不同的輸入變數（如 A 和 B），則 O(B² + A) 無法化簡，因為 A 和 B 之間沒有固定關係。

常見複雜度的增長速率（由慢到快）：

O(log x) < O(x) < O(x²) < O(x log x) < O(2ˣ) < O(x!)

Multi-Part Algorithms: Add vs. Multiply（多部分演算法）#

這是面試中常見的混淆點：

• 加法（Add）：演算法是「先做 A，做完後再做 B」→ 執行時間為 O(A + B)

for (int a : arrA) { print(a); }
for (int b : arrB) { print(b); }
// 執行時間：O(A + B)

• 乘法（Multiply）：演算法是「每次做 A 的時候，都要做 B」→ 執行時間為 O(A × B)

for (int a : arrA) {
    for (int b : arrB) {
        print(a + "," + b);
    }
}
// 執行時間：O(A * B)

在面試時非常容易搞混這兩種情況，請特別小心。

Amortized Time（均攤時間）#

ArrayList 是動態調整大小的陣列。當陣列滿了，它會建立一個容量為原來兩倍的新陣列，並將所有元素複製過去。

• 大多數情況下，插入一個元素是 O(1)
• 偶爾需要複製，是 O(N)

均攤時間（Amortized Time） 讓我們描述：雖然最壞情況偶爾發生，但它發生後很久不會再發生，所以其成本可以「均攤」。

分析：插入 X 個元素時，需要在容量 1、2、4、8、…、X 時進行複製。複製總次數為： 1 + 2 + 4 + 8 + … + X ≈ 2X

因此 X 次插入共花 O(2X) 時間，每次插入的均攤時間為 O(1)。

Log N Runtimes#

我們常在執行時間中看到 O(log N)，它從何而來？

以 Binary Search 為例：在 N 個元素的有序陣列中搜尋 x，每次比較都讓搜尋範圍減半：

N = 16 → N = 8 → N = 4 → N = 2 → N = 1

總步驟數 k 滿足：2ᵏ = N，即 k = log₂N。

關鍵規律：當問題規模在每個步驟中減半，執行時間通常是 O(log N)。在平衡二元搜尋樹中搜尋元素也是同樣道理。

log 的底數對 Big O 並不重要——不同底數的 log 之間只差一個常數因子，而常數會被省略。但對於指數，底數非常重要，2ⁿ 和 8ⁿ 相差 2^(2n) 倍，絕非常數。

Recursive Runtimes（遞迴執行時間）#

以下程式碼的執行時間是什麼？

int f(int n) {
    if (n <= 1) return 1;
    return f(n - 1) + f(n - 1);
}

許多人會錯誤地說 O(N²)。正確推導如下：

呼叫 f(4) 會產生一棵呼叫樹，每個節點有 2 個子節點，樹的深度為 N：

總節點數 = 2⁰ + 2¹ + 2² + … + 2ᴺ = 2ᴺ⁺¹ - 1，因此執行時間為 O(2ᴺ)。

關鍵規律：當一個遞迴函式有多個分支時，執行時間通常是 O(branches^depth)。

此演算法的空間複雜度為 O(N)，因為雖然共有 O(2ᴺ) 個節點，但任何時間點只有 O(N) 個節點同時存在於 call stack 上。

Examples and Exercises（範例與練習）#

以下列出書中的主要範例，讓概念更清楚：

Example 1：兩個獨立迴圈#

void foo(int[] array) {
    // 迴圈一：O(N)
    for (int i = 0; i < array.length; i++) { sum += array[i]; }
    // 迴圈二：O(N)
    for (int i = 0; i < array.length; i++) { product *= array[i]; }
}

執行時間：O(N)。遍歷兩次不影響 Big O。

Example 2：巢狀迴圈（同一個陣列）#

void printPairs(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length; j++) {
            print(array[i] + "," + array[j]);
        }
    }
}

執行時間：O(N²)。

Example 3：從 i+1 開始的巢狀迴圈#

for (int i = 0; i < array.length; i++) {
    for (int j = i + 1; j < array.length; j++) { ... }
}

總步驟數 = (N-1) + (N-2) + … + 1 = N(N-1)/2，執行時間：O(N²)。

Example 4：兩個不同的陣列#

for (int i = 0; i < arrayA.length; i++) {
    for (int j = 0; j < arrayB.length; j++) { ... }
}

執行時間：O(a × b)，不是 O(N²)！這是一個極為常見的錯誤——兩個輸入不同，都很重要。

Example 8：為變數命名清楚#

對於「排序字串陣列，再排序整個陣列」的問題，許多人錯誤地用 N 同時表示字串長度和陣列長度。應明確定義：

• s = 最長字串的長度
• a = 陣列中字串的數量

正確的執行時間：O(a × s × (log a + log s))

Example 9：平衡二元搜尋樹的遍歷#

int sum(Node node) {
    if (node == null) return 0;
    return sum(node.left) + node.value + sum(node.right);
}

每個節點被訪問一次，做固定量的工作，因此執行時間為 O(N)，N 為節點數。

Example 10：質數檢查#

boolean isPrime(int n) {
    for (int x = 2; x * x <= n; x++) {
        if (n % x == 0) return false;
    }
    return true;
}

迴圈在 x = √n 時停止，執行時間：O(√n)。

Example 12：字串的全排列#

對長度 n 的字串生成所有排列，每次函式呼叫做 O(n) 的工作，共呼叫 O(n × n!) 次，總執行時間：O(n² × n!)。

Example 13：Fibonacci（遞迴）#

int fib(int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

2 個分支，深度 N，執行時間：O(2ᴺ)。

Example 15：帶 Memoization 的 Fibonacci#

int fib(int n, int[] memo) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    else if (memo[n] > 0) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

利用快取（memoization）避免重複計算，每個值只計算一次，執行時間：O(N)。這是一種將指數時間遞迴最佳化的常見技巧。

Additional Problems（額外習題解答摘要）#