大O符號圖解與範例：時間複雜度入門

大O符號解決什麼問題

用秒數計時，只能反映某一台機器、某一種語言、某一筆輸入的情況。大O符號回答的是更有用的問題：如果輸入變成 10 倍，演算法要多做多少工作？多做 10 倍工作的演算法，與多做 100 倍工作的演算法，在規模變大時表現截然不同。

形式上，若存在常數 c 與 n₀，使得對所有 n ≥ n₀ 都有 f(n) ≤ c · g(n)，則稱 f(n) 為 O(g(n))。白話來說，當 n 夠大時，g 是 f 成長速度的上界，並且忽略常數倍數。

• n 代表輸入的規模：串列的長度、字串的字元數、圖中的節點數。
• 時間複雜度計算基本步驟的數量（比較、指派、算術運算）。
• 空間複雜度計算額外使用的記憶體，不包含輸入本身。

如何化簡運算式

先把步驟數寫成 n 的函式，再套用兩條規則：捨去常數係數，只保留主導項。

當演算法有兩個獨立的輸入時，兩者都要保留：先走訪長度為 n 的串列，再走訪長度為 m 的串列，是 O(n + m)；迴圈裡再套一層迴圈則是 O(n · m)。對數的底數在大O中並不重要，因為 log₂ n 與 log₁₀ n 只相差一個常數倍。

常見的複雜度類別

粗略的參考：在現代電腦上，Python 的簡單迴圈每秒可執行數千萬個基本步驟，編譯式語言則快得多。因此 O(n log n) 處理數百萬筆資料沒問題，O(n²) 在數萬筆左右就會變慢，而 O(2ⁿ) 超過約 40 到 60 筆資料就毫無希望了。

從 Python 程式碼判斷複雜度

先看迴圈。對輸入跑單一迴圈是 O(n)；在同一份輸入上巢狀兩層迴圈是 O(n²)；每次把剩餘範圍減半的迴圈是 O(log n)。

def first(items):            # O(1): one step, whatever the size
    return items[0]
def total(items):            # O(n): touches each item once
    s = 0
    for x in items:
        s += x
    return s
def has_duplicate(items):    # O(n^2): compares every pair
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False
def halvings(n):             # O(log n): n is halved each step
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps
print(first([7, 8]), total([1, 2, 3]), has_duplicate([1, 2, 1]), halvings(1024))
# 7 6 True 10

函式庫呼叫也有自己的成本。x in some_list 是 O(n)，x in some_set 平均是 O(1)，list.insert(0, x) 因為每個元素都要位移所以是 O(n)，sorted() 則是 O(n log n)。如果迴圈呼叫 n 次 O(n) 的操作，即使看起來只有一層迴圈，整體仍是 O(n²)。

def has_duplicate_fast(items):   # O(n) time, O(n) extra space
    seen = set()
    for x in items:
        if x in seen:            # average O(1) set lookup
            return True
        seen.add(x)
    return False
print(has_duplicate_fast([3, 1, 4, 1, 5]))   # True
print(has_duplicate_fast(list(range(10))))   # False

最佳、平均與最差情況

同一個演算法在相同規模、不同內容的輸入上，工作量可能不同，所以複雜度常分成三種情況來說明。

人們只說「X 的複雜度」時，通常指最差情況；對雜湊表與快速排序則多半指平均情況。攤銷成本（amortized cost）是第四個概念：對 Python 串列 append 時，串列擴充儲存空間的那一次是 O(n)，但在大量 append 的平均下是 O(1)。

大O、大Ω與大Θ

嚴格來說，O(n) 的演算法同時也是 O(n²)，因為 O 只是上界。日常用法中，人們寫大O，其實想表達自己所知最緊的界，也就是 Θ 所表示的意思。

常見錯誤

• 忘了內建操作的成本，例如對串列使用 in，或切片 items[1:]（會複製元素，複製 k 個元素就是 O(k)）。
• 算錯遞迴呼叫：函式對 n − 1 呼叫自己兩次，是 O(2ⁿ)，不是 O(n)。
• 忽略空間：建立大小為 n 的新串列，或遞迴深度達 n，都要花 O(n) 的記憶體。
• 寫成 O(2n) 或 O(n + 5)。兩者都化簡為 O(n)。