增长率，而不是绝对成本
大 O：度量工作成本增长率
大 O 符号度量算法成本增长率，而不是绝对成本。
大 O 所要回答的问题是：当输入大小 N 翻倍，工作量是否也翻倍？是否增加四倍？是否保持不变？
‘O’表示‘数量级’。括号内的表达式描述了增长曲线的形状。
关键复杂性类别：
- O(1) — 常数：成本不增长。示例：在数组中通过索引查找值。无论数组有 10 项还是 10 万项，一次查找仍然是一次查找。
- 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包管理器）以及1000多个其他项目中。
这不是因为它们的作者粗心大意。visited = []在N较小时被写入。代码逐渐变硬。N增长。没有人注意到，直到构建时间变为半小时。
Big O是让你能命名发生了什么的词汇——并修复它。
——
你想更深入了解吗？ 我们的unhamming课程包括一整章关于Big O、MOAD-0001（一个O(N²)缺陷，在1000多个开源项目中发现）以及为什么命名一个模式让你能在任何地方找到它。见[缺失章节：算法复杂性](/en/un/unhamming_algorithmic_complexity)。
预测构建时间
构建系统使用O(N²)的循环检测。
测量的构建时间：
- N=100个包：0.01秒
- N=1,000个包：1秒
对于O(N²)：时间与（N_new / N_old）²成比例。
对于O(N)：时间与（N_new / N_old）成比例。