02 - 怎么衡量快慢：大 O 复杂度
上一章一直说某个操作「快」或「慢」。但快慢得有个统一的说法，不然没法比较。这一章讲大 O 复杂度——它是整篇教程的「度量衡」。别怕，我们不推公式，只讲直觉。
为什么不用「跑一下看几秒」来衡量
你可能想：想知道哪个快，跑一下计时不就行了？不行，因为：
- 同一段代码，在快电脑和慢电脑上跑的时间不一样；
- 数据量小时看不出差距，数据量一大差距才暴露。
我们真正关心的是：当数据量变大时，耗时会怎么增长？ 是稳如老狗，还是爆炸式变慢？这个「增长趋势」，才是衡量快慢的关键。大 O 就是用来描述这个增长趋势的记号。
打比方：我们不关心「10 个人的时候用了几秒」，我们关心「人数翻 10 倍、100 倍时，耗时是几乎不变、还是也翻 10 倍、还是翻 100 倍」。
几种最常见的复杂度（从快到慢）
设数据量为 n（比如 n 个元素）。下面从最快到最慢排列，记住每种的「感觉」就够了。
O(1)：常数时间——最理想
不管数据有多少，操作耗时都不变。
- 例子：从数组里取第 5 个元素；查哈希表某个键。
- 感觉：一步到位，与数据量无关。 这是最快的一档。
O(log n)：对数时间——非常快
数据量翻倍，耗时只多一点点（多一步）。
- 例子：在排好序的数据里「折半查找」——每次排除一半。
- 感觉：数据涨得再多，也就多几步。 100 万个数据也就查 20 来次。极快。
O(n)：线性时间——还行
耗时和数据量成正比。数据翻倍，耗时翻倍。
- 例子：把 n 个元素挨个遍历一遍找最大值。
- 感觉：老老实实一个个过。 数据量不大时完全可以接受。
O(n log n)：比线性略慢——不错的排序水平
- 例子：主流的高效排序算法（快排、归并排序）。
- 感觉：比 O(n) 慢一点，但对「排序」这种事已经是很好的成绩了。
O(n²)：平方时间——数据一大就危险
数据翻倍，耗时翻四倍。
- 例子：两层嵌套循环，比如「拿每个元素和其他所有元素两两比较」。
- 感觉：数据小无所谓，数据一大就明显卡。 n 从 1000 涨到 10000，耗时涨 100 倍。
O(2ⁿ)：指数时间——基本没法用
数据每加 1，耗时翻倍。
- 感觉：数据稍微一多就直接算不动了，几十个元素就能让电脑跑到天荒地老。遇到这种复杂度，通常意味着思路要换。
一张直觉对比表
| 复杂度 | 名字 | 数据变大时 | 直觉评价 |
|---|---|---|---|
| O(1) | 常数 | 纹丝不动 | 完美 |
| O(log n) | 对数 | 只多一点点 | 非常快 |
| O(n) | 线性 | 成正比涨 | 可以接受 |
| O(n log n) | — | 略快于平方 | 排序的好成绩 |
| O(n²) | 平方 | 涨得很凶 | 数据大就危险 |
| O(2ⁿ) | 指数 | 直接爆炸 | 基本没法用 |
大 O 只看「增长趋势」，忽略细节
大 O 有两个「偷懒但合理」的约定：
- 忽略常数：O(2n) 和 O(100n) 都记作 O(n)。因为数据量趋大时，是「几倍」不重要，「按什么趋势涨」才重要。
- 只留最大的那项：O(n² + n) 记作 O(n²)。因为 n 很大时，n² 远远盖过 n，小项可以忽略。
大 O 是一副「望远镜」，看的是数据量趋于很大时的整体趋势，不纠结眼前的小系数。
这跟数据结构有什么关系
回到上一章：我们说「数组按位置读取快、链表按位置查找慢」，现在可以精确表达了——
- 数组按位置读取是 O(1)（一步到位）；
- 链表按位置查找是 O(n)（可能要从头走到尾）。
后面每讲一种数据结构，我们都会用大 O 标注它各个操作的快慢。你就能一眼看出它擅长什么、怕什么。
小结
- 衡量快慢不看「跑几秒」，看数据量变大时耗时的增长趋势，用大 O 表示。
- 从快到慢常见档位：O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)。
- 记住感觉：O(1) 一步到位、O(log n) 折半超快、O(n) 挨个过、O(n²) 嵌套循环数据大就危险、O(2ⁿ) 直接爆炸。
- 大 O 忽略常数、只留最高次项，是看大趋势的「望远镜」。
- 后面每种数据结构，都会用大 O 标注各操作快慢，帮你判断它擅长什么。
下一章 → 03 - 数组 vs 链表 ｜ 回到 README 目录