前两篇讲体系。这一篇开始钻算法本身，从「怎么判断一个算法好不好」讲起。
大多数人学复杂度是为了应付考试，学完就忘。真正的问题不在公式，在于不知道它拿来干什么。
一、先破一个误解
O(n²) 不等于「慢」，O(n) 不等于「快」。
举个例子：
- 一个 O(n²) 的算法，n 只有 10，那是 100 次操作——眨眼的事
- 一个 O(n) 的算法，n 是 10 亿，那是 10 亿次操作——几秒钟
所以大 O 后面那个东西，量的不是时间，是「增长」——n 变大时，代价怎么变。
这正是它的价值所在：它不预测现在，它预测将来。
你写的脚本今天跑 1 秒，明天数据涨十倍，是跑 10 秒还是跑 100 秒？大 O 回答这个问题，秒表回答不了。
二、大 O 的定义，一句话说清
形式定义是这样的（数学上严格，但第一次看容易晕）：
若存在两个正的常数 c 和 n₀，使得对所有 n ≥ n₀，都有 T(n) ≤ c·f(n)，则称 T(n) = O(f(n))。
翻译成人话：
当 n 足够大的时候，T(n) 的增长速度不会超过 f(n) 的某个倍数。
三个关键点，几乎所有人都漏：
1. 「足够大」——小数据不算数
大 O 只描述趋势，不管小规模。所以「我的数据才 100 条，用冒泡就行」这句话是对的——大 O 并没有否定它。
2. 常数被扔掉了
O(2n) 和 O(100n) 都写成 O(n)。这在实际工程里是个坑：常数可能差 50 倍。
真正跑得快的东西，往往是同一复杂度下常数更小的那个。 这就是为什么实际代码里，O(n log n) 的排序常常输给精心调过的 O(n²) 插入排序——当 n 很小的时候。
3. 只留最高阶项
n² + 100n + 10000，写成 O(n²)。因为 n 大的时候，其他项都微不足道。
| n | n² | 100n | n² 占多少 |
|---|---|---|---|
| 10 | 100 | 1,000 | 8% |
| 100 | 10,000 | 10,000 | 48% |
| 1,000 | 1,000,000 | 100,000 | 90% |
| 10,000 | 100,000,000 | 1,000,000 | 99% |
这张表就是「只留最高阶」的全部理由。
三、怎么数：三个步骤，一种方法
书上给的方法很朴素，但足够用：
- 找出输入规模 n（数据的个数？字符串长度？图的顶点数？）
- 找出基本语句（执行次数最多的那句，通常在最内层循环里）
- 数它执行了多少次，取数量级
数几次就懂了。
例一：单层循环
for (i = 0; i < n; i++)
sum += a[i]; // 执行 n 次
→ O(n)
例二：双层循环
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
sum += a[i][j]; // 执行 n² 次
→ O(n²)
例三：循环变量每次乘 2
for (i = 1; i < n; i = i * 2)
count++; // 执行 log₂n 次
→ O(log n)
为什么是 log？ 因为 i 每次翻倍，从 1 到 n 只要 log₂n 步。n = 1024 时只要 10 步。
这条最值钱：折半查找、平衡树、二分答案——所有「每次砍一半」的算法，都是 O(log n)。
例四：内外层互相独立的两个循环
for (i = 0; i < n; i++) sum1 += a[i]; // n 次
for (j = 0; j < m; j++) sum2 += b[j]; // m 次
→ O(n + m)，不是 O(n·m)。并列用加法，嵌套用乘法。
四、最好、最坏、平均：为什么要分三种
同一个算法，输入不同，代价可能差一个量级。
顺序查找找一个数：
- 正好是第一个 → 1 次比较（最好）
- 不在里面 → n 次比较（最坏）
- 平均 → n/2 次
工程上默认看最坏情况，原因很实在：
最好情况不保证下限，平均情况要假设分布，只有最坏情况是硬承诺。
你说「平均很快」，但用户碰上的那次可能正好是最坏的。做系统的人必须有最坏情况的数字，否则没法做容量规划。
例外：快排的最坏情况是 O(n²)（已经有序时），但平均 O(n log n)，所以实际都用随机化来打散。这就是为什么「随机选主元」不是锦上添花，是必需品。
五、常见复杂度，按「n 涨十倍会怎样」排序
这比记符号有用得多：
| 复杂度 | n=100 | n=1,000 | n=10,000 | 一句话印象 |
|---|---|---|---|---|
| O(1) | 1 | 1 | 1 | 跟 n 无关 |
| O(log n) | 7 | 10 | 13 | 几乎不涨 |
| O(n) | 100 | 1,000 | 10,000 | 线性，能接受 |
| O(n log n) | 664 | 9,966 | 132,877 | 排序的下限 |
| O(n²) | 10,000 | 1,000,000 | 100,000,000 | 一万条就卡了 |
| O(n³) | 1,000,000 | 10⁹ | 10¹² | 基本不能用 |
| O(2ⁿ) | 10³⁰ | — | — | n 超过 30 就别想了 |
看表记住三件事：
1. O(n log n) 是排序的「及格线」 基于比较的排序，理论下界是 Ω(n log n)——这不是「还没找到更好的」，是「靠比较不可能更好」。 想更快只能换路子：不靠比较（计数排序、基数排序）。
2. O(n²) 是分水岭 一万条数据以内还能忍，十万条就完蛋。所以「双重循环」是个危险信号——看到它的第一反应应该是「有没有办法拆开」。
3. O(2ⁿ) 是「不能用」的同义词 n=30 就是十亿次，n=40 就是万亿次。这就是为什么背包、旅行商这类问题不能用蛮力。
六、空间复杂度，别忘了一半
时间有复杂度，空间也有。但工程上两者的优先级不一样：
- 时间换空间：缓存、索引、预计算——几乎所有性能优化都在干这个
- 空间换时间：也能，但内存是硬限制，超了直接崩
一份经验：
当内存够用时，优先优化时间；当内存不够时，先优化空间再谈速度。
还有一类容易被忽略的：递归的空间开销。递归深度就是栈深度，深度一万的递归会爆栈。这是 O(n) 的空间代价，很多人算复杂度时只算了时间。
七、这些分析拿来干什么：三个真实用途
用途一：判断「这个需求能不能做」
老板要「实时查一亿条记录里的重复」。你算一下：两两比对是 O(n²)，一亿的平方——这个需求现在做不了，不是我不会，是数学不允许。 必须换方案（哈希、分块、外部排序）。
这会省下大量白费的努力。
用途二：判断「慢在哪一层」
一个接口要 2 秒。
- 数据库查询 O(n) 扫了 100 万行 → 加索引变 O(log n)
- 代码里有个嵌套循环 O(n²) → 改结构
- 网络调了 50 次 → 批量合并
不同层的问题，修法完全不同。乱猜就是在浪费时间。
用途三：判断「要不要优化」
如果现在是 O(n log n)，n 只有 1000，优化到 O(n) 只省 1 毫秒——别改，风险大于收益。
知道什么时候不优化，比知道怎么优化更值钱。
八、下一篇讲什么
分析是判断，设计是创造。
下一篇讲五个设计范式：蛮力、分治、贪心、动态规划、回溯与限界。核心不是五个模板，是「什么时候该用哪个」。
而且会给你看一个反例：同一道题，五种写法，其中最快的那个，答案是错的。
参考
- 大 O 定义、基本语句、最好/最坏/平均：见《算法设计与分析（微课版）》第 1 章（印刷 2–18）。
- 复杂度对照表与三个用途是我自己的整理。
- 排序下界、可计算性（Turing 论题、不可计算问题）、NP 完全与归约：见同书第 12 章（印刷 192 起）。
- 注：文中「O(n log n) 下界」只针对基于比较的排序，非比较排序可突破，这一点书里没有专门展开，是我补充的限定。