為什麼需要複雜度分析#

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

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

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

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

大 O 複雜度表示法#

基本概念#

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

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

推導過程#

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

// 範例一：O(n)
int cal(int n) {
    int sum = 0;      // 1 個 unit_time
    int i = 1;        // 1 個 unit_time
    for (; i <= n; ++i) {
        sum = sum + i;  // n 個 unit_time
    }
    return sum;
}
// 總時間：(2n+2) * unit_time → O(n)

// 範例二：O(n²)
int cal(int n) {
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            sum = sum + i * j;  // n² 次
        }
    }
}
// 總時間：O(n²)

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

時間複雜度分析技巧#

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

核心程式碼執行次數的 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))

常見時間複雜度#

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 變大時執行時間會急劇增加。

對數階詳解#

i = 1;
while (i <= n) {
    i = 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
int find(int[] array, int n, int x) {
    for (int i = 0; i < n; ++i) {
        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)。

均攤時間複雜度#

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

int[] array = new int[n];
int count = 0;

void insert(int val) {
    if (count == array.length) {
        // 陣列滿了，求和後清空
        int sum = 0;
        for (int i = 0; i < array.length; ++i) {
            sum += array[i];
        }
        array[0] = sum;
        count = 1;
    }
    array[count] = val;
    ++count;
}

分析：

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

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

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

空間複雜度分析#

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

void print(int n) {
    int i = 0;           // O(1) 空間
    int[] a = new int[n]; // O(n) 空間
    for (i = 0; i < n; ++i) {
        a[i] = i * i;
    }
}
// 空間複雜度：O(n)

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

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

小結#

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