課程涵蓋了什麼，又遺漏了什麼
Hamming 的課程涵蓋：類比轉數位轉換、錯誤更正、模擬、統計、數值分析，以及 n 維幾何。他以計算思維思考——訊號處理、編碼理論、數位濾波都需仰賴計算推理。
他從未系統性地教授演算法複雜度。
為什麼會有這段空白
Hamming 的心智模型形成於硬體瓶頸主導的時代。問題在於：每顆晶片上有多少個電晶體？演算法在當時可用的硬體上執行。在 N=100 時，O(N²) 演算法需要 10,000 次運算；在 N=1,000 時，需要 1,000,000 次；在 N=10,000（如今在依賴圖、社交網路與套件管理器中很常見）時，則需要 100,000,000 次。O(N) 與 O(N²) 之間的差異，在 Hamming 所處的規模下幾乎看不出來，但在他的學生所處的規模下卻是災難性的。
Donald Knuth 從 1968 年開始出版《The Art of Computer Programming》，當時 Hamming 正處於研究最活躍的時期。大 O 記號在 1970 與 1980 年代成為演算法領域的標準詞彙。Hamming 的課程雖然開設於 1995 年，但他的運算心智模型卻形成得更早。他從未更新這一章的內容。
以 Hamming 自己的標準來看，這是一項 Fundamental
Hamming 判斷一項 fundamental 的標準是：(1) 它已經存在很長一段時間，(2) 該領域的其他知識都可以用標準方法從它推導出來。
Big O 同時通過這兩項標準。成長率分析自 Knuth 之後便持續存在。從中可以推導出演算法選擇、資料結構設計，以及效能預測——實務電腦科學的大部分內容，都源自於「當 N 增加時，成本如何成長？」這個問題。Hamming 錯過了他自己領域中最持久的 fundamental。
Big O 作為一項 Fundamental
Hamming 曾教導：fundamental 會比特定技術更持久。他以微積分為例：它被發明一次，卻在數百年間適用於物理、工程、經濟與生物等領域。周邊工具來來去去，而 fundamental 則會不斷累積價值。
成本如何成長
Big O 衡量的是當輸入變大時，成本成長的方式。它關注的不是常數因子，而是成長率。兩個演算法在 N=100 時都只需「幾毫秒」，但當 N=10,000 時，若一個是 O(N) 而另一個是 O(N²)，兩者可能會相差 10,000 倍。
常見的複雜度等級
O(1) — 常數時間。 不論 N 為何，成本都相同。範例：以鍵值查詢雜湊表、依索引存取陣列、堆疊的 push/pop。將 N 加倍不會改變成本。
O(log N) — 對數。 每一步將剩餘工作量減半。範例：有序陣列的二分搜尋、遊戲引擎中的 BVH 空間查詢、平衡二元樹操作。當 N=1,000,000 時：log₂(1,000,000) ≈ 20 步。
O(N) — 線性。 成本隨輸入大小成長。範例：線性掃描清單、讀取檔案、計算集合中的項目數量。當 N=10,000 時：10,000 次操作。
O(N log N) — 線性對數。 接近線性，但略差。範例：合併排序、高效最短路徑演算法（使用堆積的 Dijkstra）。當 N=10,000 時：約 133,000 次操作。
O(N²) — 平方。 成本呈指數爆炸。範例：在同一清單的迴圈中呼叫 list.contains()、氣泡排序、朴素的兩兩比較。當 N=1,000 時：1,000,000 次操作。當 N=10,000 時：100,000,000 次操作。
O(2^N) — 指數級。 在任何有意義的規模下都無法使用。範例：暴力破解組合問題、找出所有子集合。當 N=30 時：超過 1,000,000,000 次運算。
讓它變得可見的規模
N=10 次比較：
O(N): 10
O(N²): 100
比例：10x
N=1,000 次比較：
O(N)：1,000
O(N²)：1,000,000
比例：1,000x
N=10,000 次比較：
O(N): 10,000
O(N²): 100,000,000
ratio: 10,000x當 N=10 時，差異幾乎不明顯。當 N=10,000 時，O(N²) 演算法的執行速度會慢 10,000 倍。這就是為什麼 MOAD-0001 在數十年間都未被發現：1993 年它所運行的圖形只有 50 個節點。到 2020 年，相同的程式碼卻要在擁有 50,000 個節點的相依圖上執行。
分類三種運算
將複雜度類別套用於具體運算。每個運算的核心問題是：當 N 增大時，需要執行多少次運算？
正確的程式碼，錯誤的增長曲線
以 O(N²) 時間執行的正確程式碼，會產生與 O(N) 程式碼相同的結果。測試通過、輸出相符，也沒有例外發生。缺陷隱藏在增長曲線之中。
這種特性讓 O(N²) 缺陷成為沉積性缺陷：它們在可運作的程式碼中逐漸硬化，只有當 N 超過某個門檻時才會顯現。程式碼本身並未改變，改變的是它所處的世界。
MOAD-0001：沉積性缺陷
最常見的例子：visited = [] 放在圖形遍歷迴圈內。
visited = []
for node in graph:
if node not in visited: # 每次呼叫皆為 O(N) 掃描
visited.append(node)
process(node)每次 not in visited 呼叫會掃描 0 到 len(visited)-1 個項目。N 次呼叫 × 平均掃描 N/2 個項目 = 總共 O(N²)。修正方法：一行程式碼。
visited = set() # O(1) membership test
for node in graph:
if node not in visited: # O(1) hash lookup
visited.add(node)
process(node)行為相同、輸出相同、測試也全部通過。時間複雜度從 O(N²) 降為 O(N)。在 N=1,000 時快 1,000 倍；在 N=10,000 時快 10,000 倍。
為什麼 Hamming 的時代埋下了這個問題
在早期的 Java 與 C 語言中，ArrayList（動態陣列）是預設的序列容器。雖然 Set 存在，但並非慣用寫法——開發者傾向使用熟悉的結構。1993 年，當 N=50 時，使用 visited = [] 的圖形遍歷只需數微秒。這些程式碼進入版本控制、被複製、包裝進函式庫，再透過套件管理器發佈。到 2020 年，同樣的模式卻要在擁有 50,000 個節點的相依圖上執行。
這段程式碼在 1993 年是正確的。當周遭世界的規模改變後，它才變得昂貴。Hamming 的時代因為從未明確提出「成長率」的問題，因而埋下了這類缺陷的種子。
診斷與修復
套用診斷：找出 O(N²) 模式，並確認修復方式。
命名上的改變 [BLOCK_TYPE SECTION/STEP]
在 Big O 還沒有名字之前，程式設計師只注意到「這跑得很慢」。他們進行效能分析、改寫程式，但無法把這種模式教給別人——只能指出個別案例。沒有名字的模式無法傳播。 [BLOCK_TYPE SECTION/STEP]
當 Big O 有了名字之後，資深工程師可以說「這是 O(N²)，改用 set 吧」，而初階工程師就能理解、應用，並再把這個模式教給其他人。這個名字讓模式成為可傳遞的知識單位。 [BLOCK_TYPE SECTION/STEP]
Hamming 在其他領域也觀察到這種現象。他描述了 1960 年代「spaghetti code」這個名字如何讓社群得以辨識、討論，並最終消除一類大家都曾經歷卻無人命名的缺陷。同樣的機制也適用於複雜度類別。 [BLOCK_TYPE SECTION/STEP]
Unhamming 補充了 Hamming 所遺漏的詞彙：O(1)、O(log N)、O(N)、O(N log N)、O(N²)、O(2^N)。這些名稱讓你能在閱讀程式碼時看出成長曲線、預測規模化後的效能，並精準地溝通修正方案。它們符合 Hamming 對「基本概念」的檢驗：持久且能衍生出該領域的大多數其他內容。 [BLOCK_TYPE SECTION/STEP]
從數論到電腦科學
大 O 記號並非源自電腦科學。它源自純數學——特別是數論——比 Donald Knuth 將它應用於演算法早了 74 年。
Paul Bachmann, 1894
德國數學家 Paul Bachmann 在 1894 年的著作 Die Analytische Zahlentheorie（《解析數論》）中引入了 O 記號。他需要一種簡潔的方式來表達「一個量在常數因子範圍內不會比另一個量增長得更快」。寫成「f(n) = O(g(n))」即表示：f 的增長速度最多與 g 相同。這讓數論學者能在近似誤差項的討論中，不必追蹤精確的常數。
Bachmann 當時並未考慮迴圈、資料結構或執行時間。他關注的是質數的分佈——特別是質數定理中的誤差項。
Edmund Landau, 1909
另一位德國數學家 Edmund Landau 在 1909 年的著作 Handbuch der Lehre von der Verteilung der Primzahlen（《質數分佈理論手冊》）中推廣了此記號。Landau 同時引入了相關的小 o 記號，並大量使用這類漸近符號，使得這整個符號家族被稱為 Bachmann-Landau 記號，或簡稱 Landau 記號。
長達六十年，O 記號完全存在於數學領域中。沒有程式設計師會想到它。
Donald Knuth，1968 年與 1976 年
Donald Knuth 將此記號引入電腦科學。在《電腦程式設計藝術》（The Art of Computer Programming）第一卷（1968 年）中，Knuth 使用大 O 記號描述演算法的執行時間——這是將 Bachmann 的工具直接移植到新領域。他是第一個系統性地將其應用於演算法分析的人。
1976 年，Knuth 在《SIGACT News》發表了一篇短文，標題為〈Big Omicron and Big Omega and Big Theta〉。他引入了 Omega（Ω）表示下界，以及 Theta（Θ）表示緊確界，完成了電腦科學至今仍在使用的三種符號體系。他還主張在整個領域中標準化這些符號的使用——這項刻意的標準化措施加速了其普及。
到了 1980 年代初，大 O 記號已出現在每一本演算法教科書中。到了 1990 年代，它成為面試中的標準詞彙。
74 年的旅程
1894 年 — Bachmann 在數論中引入 O
1909 年 — Landau 推廣 O、o 以及完整的記號家族
1953 — Hamming 開始在貝爾實驗室進行研究（從未學過 Big O 作為電腦科學工具）
1968 — Knuth 在《電腦程式設計藝術》第 1 卷中將 O 應用於演算法分析
1976 — Knuth 加入 Omega 與 Theta；主張標準化
1980 年代 — Big O 進入所有電腦科學課程
1993 — MOAD-0001 沉積層在生產程式碼中形成
1995 — Hamming 教授其課程的最後一版；從未涵蓋 Big O
2026 — MOAD-0001 在 1,000 多個開源專案中被發現Bachmann 的工具在純數學領域沉寂了 74 年，數學家人人可見，程式設計師卻無人知曉。Knuth 看見了移植的契機。同一時代的 Hamming 與同一計算社群合作，卻從未將它納入課程。
Why Knuth's Standardization Mattered
Knuth 1976 年的論文不只引進了 Omega 與 Theta，還主張該領域需要一致的符號，不一致的符號會造成實質傷害。不同教科書對 O 的解讀各異——有時指上界、有時指近似、有時未說明常數是否重要。Knuth 將這些問題清理乾淨。
這正是 Hamming 的「模式命名」機制應用在符號本身。在 Knuth 標準化這些符號之前，工程師無法在教科書、論文或團隊之間精確傳達複雜度主張。標準化之後，「this runs in O(N log N)」無論由誰說出，都只有單一確切意義。
Knuth 也提供了非正式的翻譯：「O(f(n)) 表示執行時間最多是 f(n) 的常數倍，且對所有足夠大的 n 都成立。」這種「上界、常數因子、針對大規模輸入」的解讀，成為每位程式設計師學習的標準直覺。