成本是如何增长的

大 O 测量的是成本增长如何随着输入的增长而增长，而不是常数因子——而是增长率。两个运行时间都为‘几毫秒’的算法，在 N=100 时可能在 N=10,000 时差异化因子为 10,000，如果一个运行时间为 O(N) 时间，另一个运行时间为 O(N²)。

常见复杂性类别

O(1) — 常数。 无论 N 有多大，成本都相同。例如：通过键查找哈希表、通过索引访问数组、堆栈推入/弹出。将 N 乘以 2，结果不会改变。

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
  ratio:  10x

N=1,000比较：
  O(N):   1,000
  O(N²):  1,000,000
  ratio:  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年隐藏了这么长时间：它运行的图在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 时：1000× 更快。在 N=10,000 时：10,000× 更快。

为什么汉明的时代播下了这个种子

在早期的 Java 和 C 语言中，ArrayList（动态数组）是默认的顺序容器。集合存在但不符合常规——开发人员会 reaches for what was familiar。1993 年的图遍历在 N=50 时运行在微秒级别与 visited = []。这个代码进入了版本控制，复制了，包装成了库，通过包管理器分发。到 2020 年，这个模式在 50,000 个节点的依赖图上运行。

1993 年，这个代码是正确的。当周围的世界发生变化时，它变得昂贵。汉明的时代通过从未提到增长率的问题，播下了这个缺陷类的种子。

诊断与修复

应用诊断：找到 O(N²) 模式，识别修复方法。

命名变化

在 Big O 有名字之前，程序员注意到 '这运行得慢'。他们进行了性能分析。他们重写了代码。但他们无法传授这个模式——他们只能指向具体的例子。一个没有名字的模式无法传播。

在 Big O 有名字之后，一位资深工程师可以说 '这是一种 O(N²)，用一个集合来替换它'，而一位初级工程师也能理解、应用并传授这个模式。这个名字使得模式变成了可传递的知识单位。

Hamming 在其他领域了解到了这种动态。他描述了如何在 1960 年代将 '烂代码' 命名，社区才能够识别、讨论并最终根除一种每个人都经历过但没有人给予名字的缺陷。这个机制同样适用于复杂性类别。

Unhamming 添加了 Hamming 省略的词汇：O(1)、O(log N)、O(N)、O(N log N)、O(N²)、O(2^N)。这些名字让你在阅读代码时看到增长曲线，预测大规模的性能，并精确地沟通解决方案。它们满足了 Hamming 自己对基本概念的测试：具有持久性，并产生大部分剩余领域的知识。

从数论到计算机科学

Big O 符号没有在计算机科学领域产生。它起源于纯数学——特别是在数论领域——比 Donald Knuth 将其用于算法的时间早 74 年。

保罗·巴赫曼，1894

保罗·巴赫曼是一位德国数学家，他在 1894 年的书籍《分析性数论》中引入了 O 符号。他需要一种紧凑的方式来表示一个数量增长不超过另一个数量，除去常数因子。写作 'f(n) = O(g(n))' 表示：f 的增长速度最多不超过 g。这使得数论学者能够在近似值中进行关于误差项的推理，而无需跟踪确切的常数。

巴赫曼在思考循环、数据结构或执行时间时。他在思考质数的分布——特别是在质数定理中的误差项。

埃德蒙德·兰达乌，1909

埃德蒙德·兰达乌，另一位德国数学家，在 1909 年的《分配分布手册》中使得这个符号流行。兰达乌还引入了与之相关的符号 o（小写-o），并以这种渐近符号的广泛使用使得这一家族被称为巴赫曼-兰达乌符号或简称兰达乌符号。

在六十年里，O表示完全局限在数学领域。没有程序员会考虑它。

Donald Knuth, 1968 & 1976

Donald Knuth将这个符号引入了计算机科学。《计算机程序设计技巧》(第一卷,1968)中，Knuth使用O表示法来描述算法的运行时间——这直接将Bachmann的工具移植到了一个新的领域。他是第一个系统地将其应用于算法分析的。

1976年，Knuth在《SIGACT News》上发表了一篇短文《大Omicron、大Omega和大Theta》。他引入了Omega表示下界和Theta表示紧界，完成了计算机科学今天使用的三元词汇。他还主张在该领域统一使用这些符号——这一明确的标准化行为加速了采用。

到20世纪80年代初，大O已经出现在了每一本算法书籍。到了20世纪90年代，它已经成为标准的面试词汇。

74年的旅程

1894年 — Bachmann引入O表示法
1909年 — Landau普及了O、o以及整个表示法家族
1953年 — Hamming在贝尔实验室开始研究(从未将大O作为CS工具学习)
1968年 — Knuth将O应用于算法分析《TAOCP》第一卷
1976年 — Knuth添加了Omega和Theta，主张标准化
1980年代 — 大O进入了所有CS课程
1993年 — MOAD-0001沉积层在生产代码中形成
1995年 — Hamming教授最后一节课;从未涉及大O
2026年 — MOAD-0001在1000+开源项目中发现

Bachmann的工具在纯数学中度过了74年，数学家能看到它，但程序员却看不见。Knuth看到移植。Hamming在同一时期，同一计算机社区中工作，但从未将其纳入课程。

为什么Knuth的标准化很重要

Knuth在1976年的论文不仅引入了Omega和Theta，它还主张该领域需要一致的表示法，并指出不一致的表示法对程序员有害。不同的教科书中，O表示法的含义不同——有时表示上界，有时表示近似值，有时没有说明常数是否重要。Knuth清除了这些问题。

这就是汉明的模式命名动态应用于符号本身。 trước Knuth 标准化符号，工程师无法在教科书、论文或团队之间精确地传达复杂性声明。 after 标准化,'this runs in O(N log N)' 无论谁说，都带有确切的含义。

Knuth 还为非正式翻译做出了贡献:'O(f(n)) 表示运行时间在所有足够大的 n 时不超过一个常数倍的 f(n)。' 这一解释——对于大输入的上界，乘以常数因子——成为每个程序员都要学的标准直觉。