成長率，不是絕對成本
Big O: 衡量成本增長的速度
Big O 記號衡量演算法成本的成長率——不是絕對成本。
Big O 回答的問題是：當輸入大小 N 加倍時，工作量會加倍嗎？四倍？還是保持不變？
'O' 代表『數量級』。括號內的表達式描述成長曲線的形狀。
主要複雜度類別：
- O(1) — 常數：成本不隨輸入而增長。例如：通過索引查找陣列中的值。無論陣列有 10 個項還是 1000 萬個項，一次查找就是一次查找。
- O(N) — 線性：成本隨輸入而增長。例如：一次讀取列表中的每個項。列表加倍，讀取次數加倍。
- O(N²) — 二次方：成本隨輸入的平方而增長。例如：將每個項與其他每個項進行比較。N 加倍，工作量四倍。
成長比較表：
| N | O(1) | O(N) | O(N²) |
|---|---|---|---|
| 10 | 1 | 10 | 100 |
| 100 | 1 | 100 | 10,000 |
| 1,000 | 1 | 1,000 | 1,000,000 |
在 N=10 時差異看起來很小。在 N=1,000 時差距變得巨大。
比較 O(N) 和 O(N²)
使用上面的成長比較表。
在 N=1,000：O(N) 需要 1,000 次運算。O(N²) 需要 1,000,000 次運算。
代碼結構如何揭示複雜度
如何從代碼中辨認 Big O
Big O 隱藏在你代碼的形狀中。四種模式涵蓋了大多數情況：
單一循環遍歷 N 個項：O(N)
# O(N): 遍歷列表一次
for item in list_of_n_items:
process(item)嵌套循環，每個都遍歷 N 個項：O(N²)
# O(N²): 每個項與其他每個項配對
for item_a in list_of_n_items:
for item_b in list_of_n_items:
compare(item_a, item_b)常數時間查找：O(1)
陣列索引訪問、雜湊表查找——無論大小如何都是一步。
分治法（每一步將問題減半）：O(log N)
二分查找：每次檢查都將剩餘項減半。
---
隱藏的 O(N²)：循環內的列表
# 這看起來像 O(N) 但實際上是 O(N²)
visited = []
for item in list_of_n_items:
if item not in visited: # 掃描所有 visited：O(N)
visited.append(item) # 整個循環：O(N²)if item not in visited 這一行在每次迭代中掃描 visited 的每個元素。列表掃描成本是 O(N)。一個運行 N 次的循環，每次做 O(N) 的工作：O(N) × O(N) = O(N²)。
這個模式出現在 1,000 多個開源項目中。修復只需一個字元：將 visited = [] 替換為 visited = set()。集合成員測試成本是 O(1)，不是 O(N)。一個改變。相同的結果。在 N=1,000 時快 1,000 倍。
分類和修復這個代碼
閱讀這個代碼：
result = []
for name in student_names:
if name not in result:
result.append(name)理論遇上實踐
實際應用中的 Big O
Big O 不只是理論。它區分了以秒為單位完成的程序和以 17 分鐘為單位完成的程序——在完全相同的任務上。
真實例子：構建系統中的依賴循環檢測。
當你安裝軟件時，你的電腦解析一個依賴圖：包 A 需要 B，B 需要 C，以此類推。構建系統檢查這個圖是否有循環。
O(N²) 的循環檢測演算法在 N=100 個包時工作得很好。在 N=50,000 個包時（一個真實項目）：它需要 17 分鐘。O(N) 修復：10 秒。
這個確切的缺陷存在於 GHC（Haskell 編譯器）、pip（Python 包管理器）、Maven（Java 構建系統）、Cargo（Rust 包管理器）& 1,000 多個其他項目中。
不是因為他們的作者粗心大意。visited = [] 在 N 很小時被寫入。代碼固化了。N 增長了。沒人注意，直到構建花了半個小時。
Big O 是讓你命名發生了什麼的詞彙——& 修復它。
---
想深入了解嗎？ 我們的 unhamming 課程包括一個完整的 Big O 章節、MOAD-0001（一個在 1,000 多個開源項目中發現的真實 O(N²) 缺陷）、& 為什麼命名一個模式讓你在各處找到它。參見 缺失的章節：演算法複雜度。
預測構建時間
一個構建系統使用 O(N²) 循環檢測。
測量的構建時間：
- N=100 個包：0.01 秒
- N=1,000 個包：1 秒
對於 O(N²)：時間按 (N_new / N_old)² 縮放。
對於 O(N)：時間按 (N_new / N_old) 縮放。