增长率，而不是绝对成本
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) 的比例增长。