课程涵盖了什么，又遗漏了什么
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 年开始出版《计算机程序设计艺术》——同年 Hamming 正处于研究高峰期。大 O 记号在 20 世纪 70 年代和 80 年代成为标准的算法词汇。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 时：超过 10 亿次操作。
让它变得可见的规模
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) 成员测试
for node in graph:
if node not in visited: # O(1) 哈希查找
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²) 模式，确定修复方案。
命名带来的改变
在 Big O 尚未命名之前，程序员们只注意到“运行速度慢”。他们进行性能分析，重新编写代码。但他们无法传授这种模式——只能指出具体的实例。没有名称的模式无法传播。
在 Big O 有了名称之后，高级工程师可以说“这是 O(N²)，用集合替换它”，初级工程师就能理解、应用，并反过来传授这种模式。名称使模式成为可传递的知识单元。
Hamming 在其他领域也了解这种动态。他描述了 20 世纪 60 年代命名“意大利面条代码”（spaghetti code）如何让社区识别、讨论并最终消除一类缺陷——每个人都经历过，但之前没有人命名。同样的机制也适用于复杂度类别。
Unhamming 补充了 Hamming 遗漏的词汇：O(1)、O(log N)、O(N)、O(N log N)、O(N²)、O(2^N)。这些名称让你能在阅读的代码中看到增长曲线，预测大规模下的性能，并精确地交流修复方案。它们满足了 Hamming 自己对基本概念的测试：持久且能生成该领域的大部分其他内容。 [TITLE who_coined_big_o/]
从数论到计算机科学
大 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 将该记号引入计算机科学。在《计算机程序设计艺术》（第 1 卷，1968 年）中，Knuth 使用 O 记号描述算法的运行时间——将 Bachmann 的工具直接移植到新领域。他是第一个系统地将该记号应用于算法分析的人。
1976 年，Knuth 在 SIGACT News 上发表了一篇题为《Big Omicron and Big Omega and Big Theta》的短文。他引入了 Omega（Ω）表示下界、Theta（Θ）表示紧界，完善了计算机科学至今仍在使用的三符号体系。他还主张在整个领域内标准化这些符号的使用——这一有意识的标准化举措加速了它们的普及。
到 20 世纪 80 年代初，Big O 已出现在每一本算法教材中。到 90 年代，它已成为面试中的标准词汇。
74 年的历程
1894 年 — Bachmann 在数论中引入 O
1909 年 — Landau 推广 O、o 及其完整符号体系
1953 — Hamming 开始在贝尔实验室进行研究（从未将 Big O 作为计算机科学工具学习）
1968 — Knuth 在《TAOCP》第 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 与同一计算社区合作，却从未将其纳入课程。
为什么 Knuth 的标准化至关重要 [BLOCK_TYPE SECTION/STEP]
Knuth 1976 年的论文所做的远不止引入 Omega 和 Theta。它论证了该领域需要一致的记号，而不一致的记号正在造成实际危害。不同教材对 O 的含义各不相同——有时指上界，有时指近似，有时未说明常数是否重要。Knuth 清理了这些混乱。 [BLOCK_TYPE SECTION/STEP]
这是 Hamming 的“模式命名”机制在记号层面的应用。在 Knuth 标准化符号之前，工程师无法在教材、论文或团队间精确交流复杂度主张。标准化之后，“this runs in O(N log N)”无论由谁说出，都只具有唯一含义。 [BLOCK_TYPE SECTION/STEP]
Knuth 还给出了非正式的解读：“O(f(n)) 表示运行时间最多是 f(n) 的常数倍，对于所有足够大的 n。”这种“上界、常数因子、针对大输入”的理解，成为每位程序员学习的标准直觉。