準時完成的演算法：複雜度檢查清單

你寫了一個函式，在測試資料上執行，運作正常。接著它進入生產環境——50 萬筆資料而非 500 筆——請求就逾時了。這種情況不斷發生，幾乎都是隱藏在看似合理的程式碼裡的複雜度問題。

為什麼你的筆電騙了你

O(n²) 演算法在 100 個項目上執行 10,000 次操作。那在任何機器上都是瞬間完成。同樣的演算法在 100,000 個項目上執行，你會有 100 億次操作——花費幾分鐘或幾小時而非毫秒。n 到 n² 的跳躍在 n 變大時才顯得危險，正因為如此它才會溜過程式碼審查和本地測試。

經典例子：用巢狀迴圈檢查重複項目。

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

這是 O(n²)。改用集合：

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

現在是 O(n)。集合查詢平均是 O(1)，所以整個函式線性擴展而非二次方擴展。在 10,000 個項目上，這意味著 1 億次比較和 1 萬次比較的差別。

最佳化前先測量

別猜測。用 timeit 做微型效能測試：

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

針對更大的函式，用 cProfile 分析：

python -m cProfile -s cumulative myscript.py

查看 cumtime 欄位。如果某個函式佔了 90% 的執行時間，那就是你的目標。最佳化不是bottleneck 的程式碼是浪費時間，還會增加複雜度卻沒有收益。

會悄悄變慢的常見模式

重複的列表成員檢查。 if x in my_list 對列表來說是 O(n)，但對集合或字典平均是 O(1)。如果你在迴圈內檢查成員資格，O(n) 檢查在 O(n) 迴圈內就是 O(n²) 整體複雜度。把列表換成集合，你就回到 O(n)。

在迴圈中串接字串。 在 Python 中，迴圈中的 result += chunk 在最壞情況下是 O(n²)，因為字串不可變，每次串接都複製整個字串。改用 ''.join(chunks)——它一次建立字串。

不必要的排序。 sorted() 是 O(n log n)。如果你在迴圈內呼叫它只是為了找每次迭代的最大或最小值，用 max()/min()（O(n)），或者如果你需要重複找極值就用堆積（heapq）。heapq.nlargest(k, data) 是 O(n log k)，當 k 很小時比排序整個列表便宜得多。

沒有備忘的遞迴函式。 樸素遞迴斐波那契是 O(2ⁿ)，因為它一再重算相同的子問題。加上 functools.lru_cache 就降到 O(n)：

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

快速讀懂真實程式碼的 Big O

計算同一輸入上的巢狀迴圈——那通常就是你的指數。單層迴圈是 O(n)。迴圈內的迴圈是 O(n²)，除非內層迴圈的範圍在縮小（像冒泡排序的最佳化形式，最壞情況還是 O(n²) 但比較次數少）。將問題分成兩半的遞迴呼叫，像二分搜尋或合併排序，指向 O(log n) 或 O(n log n)。每層分出多個呼叫的遞迴呼叫，像樸素斐波那契，指向指數時間——一個強烈信號表示你需要備忘或反覆重寫。

好習慣是：在你對使用者面對的資料寫巢狀迴圈或遞迴前，問自己 n 在生產中現實上可能有多大，而不是你測試檔案裡的大小。如果 n 可能達到六位數，O(n²) 解決方案在上線前需要再檢視一次。

如需更多複雜度分析、排序演算法和分析工具的資訊，查看 Korra Studio 上的 Python 和計算機科學區段。