1.2 複雜度分析入門#

概念說明#

比較兩個程式誰比較快，最直接的方法是實際計時，但計時結果會受機器、語言、輸入大小影響，不夠客觀。演算法分析改用數學方式，統計「基本操作執行的次數」隨輸入大小 n 成長的趨勢，這就是複雜度分析。

常用的記號是大 O 符號（Big-O），描述最壞情況下的成長上限。常見的成長等級由快到慢排列如下：

大 O	名稱	n=1000 時大約的操作次數	典型例子
O(1)	常數	1	存取陣列元素
O(log n)	對數	10	二元搜尋
O(n)	線性	1,000	走訪一次串列
O(n log n)	線性對數	約 10,000	合併排序
O(n²)	平方	1,000,000	雙層迴圈
O(2ⁿ)	指數	天文數字	列舉所有子集合

注意：大 O 只看「成長趨勢」，常數係數與低次項會被省略。例如 3n² + 100n + 500 記作 O(n²)。當 n 很大時，O(n log n) 的演算法終將勝過 O(n²)，即使前者的常數比較大。

分析方法：數迴圈#

分析技巧很樸素——檢查每段程式碼執行了幾次：

# O(1)：與 n 無關
def first(a):
    return a[0]

# O(n)：迴圈跑 n 次
def total(a):
    s = 0
    for x in a:
        s += x
    return s

# O(n²)：雙層迴圈，內層對每個外層元素都跑 n 次
def pairs(a):
    c = 0
    for i in range(len(a)):
        for j in range(len(a)):
            c += 1
    return c

# O(log n)：每次迴圈 n 減半
def halves(n):
    count = 0
    while n > 1:
        n = n // 2
        count += 1
    return count

規則口訣：順序執行取相加（保留最大項）、巢狀執行取相乘。若迴圈次數每次「減半」或「乘以一半」，通常是 O(log n)；若資料結構的操作「沿著一條路往下走，每步排除一半」，也是對數級。

最壞、平均與均攤#

同一個操作可能有好幾種分析角度：

最壞情況（worst case）：保證不會更慢，最常用於大 O。
平均情況（average case）：對所有輸入取期望值，例如雜湊表查詢平均 O(1)。
均攤分析（amortized）：把偶爾很貴的成本分攤到多次操作上。例如 Python 串列 append 平均是 O(1)——雖然偶爾擴容時要搬移整個陣列（O(n)），但很久才發生一次，攤提後每次操作近乎常數。

空間複雜度#

除了時間，空間複雜度統計程式需要多少額外記憶體。例如合併排序需要 O(n) 的暫存陣列，是「用空間換穩定效率」；某些遞迴演算法的空間成本主要來自呼叫堆疊深度，例如二元樹走訪的遞迴版本需要 O(h) 的堆疊空間（h 為樹高）。

用程式實測成長趨勢#

我們可以寫個小實驗，觀察 O(n²) 與 O(n log n) 的差距：

import random, time

def max_pair_sum_quadratic(a):      # O(n²)
    best = 0
    for i in range(len(a)):
        for j in range(len(a)):
            if a[i] + a[j] > best:
                best = a[i] + a[j]
    return best

def max_pair_sum_linear(a):          # O(n)：找最大與次大即可
    m1 = m2 = float('-inf')
    for x in a:
        if x > m1:
            m2, m1 = m1, x
        elif x > m2:
            m2 = x
    return m1 + m2

for n in [1000, 5000, 20000]:
    data = [random.randint(0, 10**9) for _ in range(n)]
    t = time.perf_counter()
    max_pair_sum_linear(data)
    linear_time = time.perf_counter() - t
    print(f"n={n:6d}  線性版: {linear_time:.5f} 秒（平方版在此規模會慢 n 倍以上）")

線性版跑 20 萬筆都游刃有餘，平方版在 2 萬筆時就已經要跑數秒——這就是複雜度的威力：它告訴你程式在資料變大時的命運。

複雜度分析#

分析以下函式的時間複雜度：for i in range(n): j = 1; while j < n: j *= 3。
二元搜尋在長度為 n 的有序陣列中查找，為什麼是 O(log n)？請說明每次查找後「搜尋範圍」如何變化。
「append 平均 O(1) 但最壞 O(n)」屬於哪一種分析？請用自己的話解釋均攤分析的精神。