為什麼需要複雜度分析#

你可能會想：把程式碼跑一遍，統計執行時間和記憶體佔用不就好了嗎？

這種方法叫做事後統計法，但有重大局限性：

1. 測試結果依賴測試環境：同樣的程式碼在 i9 和 i3 處理器上執行速度差異巨大
2. 測試結果受資料規模影響：小規模資料下，插入排序可能比快速排序還快

我們需要一個不用具體測試資料，就能粗略估計演算法執行效率的方法——這就是複雜度分析。

大 O 複雜度表示法#

基本概念#

大 O 時間複雜度表示的是：程式碼執行時間隨資料規模增長的變化趨勢。

• 全稱：漸進時間複雜度（asymptotic time complexity）
• 不是實際執行時間，而是增長趨勢

推導過程#

假設每行程式碼執行時間為 unit_time：

// 範例一：O(n)
fun cal(n: Int): Int {
    var total = 0          // 1 個 unit_time
    var i = 1              // 1 個 unit_time
    while (i <= n) {
        total += i         // n 個 unit_time
        i++
    }
    return total
}
// 總時間：(2n+2) * unit_time → O(n)

// 範例二：O(n²)
fun cal(n: Int): Int {
    var total = 0
    for (i in 1..n) {
        for (j in 1..n) {
            total += i * j  // n² 次
        }
    }
    return total
}
// 總時間：O(n²)

當 n 很大時，低階、常量、係數對增長趨勢影響很小，都可以忽略。只需記錄最大量級。

為什麼可以放心忽略常數？#

「一顆西瓜加兩粒芝麻，還是約等於一顆西瓜」——這在數學上當然不成立，但複雜度分析刻意這樣定義。原因是：它要強迫我們把注意力放在「數量級」的差異上，而捨棄常數因子。

常數哪怕差上千百倍，也只是芝麻；數量級的差異才是西瓜。當 n 夠大，10000 × n log n 終究會遠小於 0.00001 × n²。所以複雜度比較的是漸進行為，而不是小規模下的實測值。

這背後是高德納（Knuth）奠定的三個核心思想：

1. 只考慮 n ➡️ ∞ 的大數據情況——計算機本來就是為處理大數據而生。
2. 區分「不隨 n 變的常數因子」與「隨 n 變的因子」，只看後者。
3. 數量級只要差一點，n 一大就能差出萬億倍。

嚴謹一點：Big O、Ω、Θ#

學術上其實有三個記號，工程面試常被混淆：

業界口語說的「Big O」，其實多半指的是 Θ（緊界）。面試時要給出最緊的那個估計：把 O(n) 的演算法說成 O(n²) 雖然「沒說錯」，卻會讓人覺得你沒看透。另外要注意，O、Ω、Θ 講的是「上下界」，與「最好／最壞／平均情況」是兩個正交的維度，別混為一談。

時間複雜度分析技巧#

只關注迴圈執行次數最多的程式碼#

核心程式碼執行次數的 n 的量級，就是整段程式碼的時間複雜度。

加法法則#

總複雜度等於量級最大的那段程式碼的複雜度。

T(n) = T1(n) + T2(n) = max(O(f(n)), O(g(n)))

即使某段程式碼迴圈 10000 次，只要跟 n 無關，都是常量級，可以忽略。

乘法法則#

巢狀程式碼的複雜度等於內外複雜度的乘積。

T(n) = T1(n) × T2(n) = O(f(n) × g(n))

範例：雙層 for 迴圈 = O(n) × O(n) = O(n²)；外層 O(n)、內層 O(log n) 的組合 = O(n log n)。

遞迴的兩條黃金規律#

遞迴的複雜度不好直接數迴圈，但有兩條規律幾乎涵蓋所有情況：

• 問題規模每步減半 ➡️ O(log n)（如二分查找）。
• 多分支遞迴 ➡️ O(branches^depth)——分支數的深度次方。例如費氏數列每層分裂成 2 個子呼叫、深度 n，故為 O(2ⁿ)。

對數的「底數」可以忽略（log₂ 與 log₁₀ 只差常數），但指數的底數絕對不能忽略：2ⁿ 與 8ⁿ 之間差了 2^(2n) 倍，是天差地別。

多個輸入變數，不要硬湊成一個#

當演算法依賴兩個獨立的規模時，複雜度也要保留兩個變數：

• 走訪一個 A×B 的矩陣是 O(A·B)，不能因為「都是規模」就寫成 O(N²)。
• 對「a 個字串、每個長 s」做排序，正解是 O(a · s · (log a + log s))，把 a 與 s 分清楚。

替變數取清楚的名字（a = 陣列長度、s = 字串長度），是避免複雜度算錯的第一步。這也是面試最常見的失分點之一。

常見時間複雜度#

flowchart LR
    subgraph 多項式時間["✅ 多項式時間（可接受）"]
        A["O(1)<br/>常數階"] --> B["O(log n)<br/>對數階"]
        B --> C["O(n)<br/>線性階"]
        C --> D["O(n log n)<br/>線性對數階"]
        D --> E["O(n²)<br/>平方階"]
    end

    subgraph 指數時間["❌ 非多項式時間（極低效）"]
        F["O(2ⁿ)<br/>指數階"]
        G["O(n!)<br/>階乘階"]
    end

    E -.->|"效率急劇下降"| F
    F --> G

    style A fill:#c8e6c9
    style B fill:#c8e6c9
    style C fill:#fff9c4
    style D fill:#fff9c4
    style E fill:#ffe0b2
    style F fill:#ffcdd2
    style G fill:#ffcdd2

非多項式量級（O(2ⁿ)、O(n!)）的演算法極其低效，當 n 變大時執行時間會急劇增加。

對數階詳解#

var i = 1
while (i <= n) {
    i *= 2  // 每次乘以 2
}

變數 i 的取值：1, 2, 4, 8, … 2^x

當 2^x = n 時結束，即 x = log₂n，所以複雜度為 O(log n)。

不管底數是 2、3 還是 10，對數之間可以互相轉換（log₃n = log₃2 × log₂n），係數可以忽略，所以統一表示為 O(log n)。

四種複雜度分析#

最好情況時間複雜度#

在最理想的情況下執行程式碼的時間複雜度。

// 查找元素 x
fun find(array: IntArray, x: Int): Int {
    for (i in array.indices) {
        if (array[i] == x) {
            return i
        }
    }
    return -1
}
// 最好情況：第一個元素就是 x → O(1)

最壞情況時間複雜度#

在最糟糕的情況下執行程式碼的時間複雜度。

// 同上範例
// 最壞情況：x 不存在 → O(n)

平均情況時間複雜度#

也叫加權平均時間複雜度或期望時間複雜度。

考慮所有情況發生的機率，計算加權平均值：

• x 在陣列中的機率：1/2
• x 在位置 0~n-1 的機率：1/(2n)
• x 不在陣列中的機率：1/2

加權平均後，平均時間複雜度仍為 O(n)。

均攤時間複雜度#

應用場景：大部分操作時間複雜度很低，只有個別情況很高，且操作之間有時序關係。

val array = IntArray(n)
var count = 0

fun insert(value: Int) {
    if (count == array.size) {
        // 陣列滿了，求和後清空
        var total = 0
        for (i in array.indices) {
            total += array[i]
        }
        array[0] = total
        count = 1
    }
    array[count] = value
    count++
}

分析：

• 大部分插入：O(1)
• 陣列滿時：O(n)
• 規律：1 次 O(n) 後，跟著 n-1 次 O(1)

攤還分析：把 O(n) 的耗時平攤到 n-1 次 O(1) 操作上，均攤時間複雜度為 O(1)。

能應用均攤分析的場合，均攤時間複雜度通常等於最好情況時間複雜度。

最經典的真實場景是 ArrayList / Vector 動態擴容（見陣列章節）：擴容那次是 O(n)，但平攤到後續每次 add 都只算 O(1)。

空間複雜度分析#

漸進空間複雜度：演算法的儲存空間與資料規模之間的增長關係。

fun printSquares(n: Int) {
    val a = IntArray(n)      // O(n) 空間
    for (i in 0 until n) {   // i：O(1) 空間
        a[i] = i * i
    }
}
// 空間複雜度：O(n)

常見空間複雜度：O(1)、O(n)、O(n²)

空間複雜度分析比時間複雜度簡單很多，O(log n) 這類對數階空間複雜度平時很少用到。

換個角度：問題的「複雜度下界」#

前面都在問「我寫的演算法有多快」，但有一個更高明的問題是：這個問題本身，至少需要做多少工作？

這就是「複雜度下界」的思維。評估一道題時，先別急著想解法，先問：

「不管用什麼演算法，理論上至少要花多少時間？」

舉例：要找出一個陣列的最大子區間和，你至少得把每個元素看過一次，否則漏看的那個可能正是答案——所以下界不可能低於 O(n)。一旦你寫出了 O(n) 的解，就能確信「到此為止、不必再找更快的了」。

下界思維有兩個用途：（1）在動手前就知道最好能做到多快，避免在已是最優的解上空轉；（2）反過來檢查自己目前的解「離下界還有多遠」，判斷有沒有優化空間。

為什麼下界常常是 O(log n) 和 O(n log n)？#

下界並非憑空而來，它的根源是資訊量。

把問題想成「猜謎」：每問一個是非題，最多得到 1 個位元（bit）的資訊。要從 N 種等可能的答案中鎖定一個，至少需要 log₂N 個位元——也就是 log₂N 次提問。

• 這正是二分查找 O(log n) 的本質：每次比較把可能範圍砍半（得到 1 bit），所以 log n 次必然收斂。
• 也是比較排序下界 O(n log n) 的本質：n 個元素有 n! 種排列，要區分它們至少需要 log₂(n!) ≈ n log n 次比較。任何「靠兩兩比較」的排序，都不可能突破這道牆。

一句話記住：世界盃 32 強猜冠軍，每次問「在不在前一半」，最多 5 次就能猜中——因為 log₂32 = 5。資訊量決定了下界，這不是「演算法剛好這麼快」，而是「任何演算法都不可能更快」。

養成「粗估」的習慣#

工程上常需要不用跑程式就快速判斷量級。幾個好用的心算工具：

• n = 10⁶ 時：O(n³) 要算上好幾十年、O(n²) 要幾小時、O(n log n) 不到一秒、O(n) 只要幾十毫秒。這組數字能讓你瞬間判斷一個解「能不能上線」。
• 2¹⁰ ≈ 1000：所以連續翻倍 30 次就破十億，估算成長性問題時很實用。
• 用兩種方法估同一個量，若結果一致，就對估算更有信心。

小結#

複雜度分析關鍵在於「熟練」。多看案例、多分析，就能做到「無招勝有招」——看到程式碼就能快速判斷複雜度。