1
先讲一个翻字典的故事
在一本 1000 页的字典里找一个词，有两种做法：
- 笨办法：从第 1 页开始一页页翻。运气差要翻 1000 页；字典加厚到 2000 页，工作量翻倍。
- 聪明办法：从中间翻开，判断要找的词在前半还是后半，砍掉一半；再对半砍……最多翻 10 次（2¹⁰ = 1024）。字典加厚一倍，只多翻 1 次。
数据变多时，两种做法的工作量增长方式完全不同——这就是大O要刻画的「增长」。
大O不关心你开的是跑车还是自行车（那是电脑性能），它关心的是「路有多长」：是绕小区一圈，还是环游地球？做法的差距，再快的电脑也救不回来。
2
常见的几个「体型」
设数据量是 n（比如 1000 个名字），看各体型的工作量：
| 记号 | 名字 | 直白解释 | n=1000 时大约 |
|---|---|---|---|
| O(1) | 常数 | 不管 n 多大，都只做固定几步 | 1 步 |
| O(log n) | 对数 | 每做一步就把问题砍一半（翻字典法） | 约 10 步 |
| O(n) | 线性 | 数据翻倍，工作量翻倍（一页页翻） | 1000 步 |
| O(n log n) | 线性对数 | 高效排序的典型水平 | 约 10000 步 |
| O(n²) | 平方 | 每人都和所有其他人握手一次 | 1000000 步 |
| O(2ⁿ) | 指数 | 每加一个数据，工作量翻倍——灾难 | 天文数字 |
O(1)是「闭着眼从口袋摸钥匙」：口袋再大也是一摸。O(n)是「挨个问全班同学」：人多问得久。O(n²)是「全班每人跟每人聊一句」：人一多，爆炸。O(log n)是「二分法找答案」：世界再大，也就多问几次。
3
为什么平方和指数这么可怕？
感受一下差距。假设电脑每秒做 10 亿次基本操作，n = 100 万：
- O(n)：100 万步 → 瞬间完成
- O(n²)：1 万亿步 → 约 17 分钟
- O(2ⁿ)：2¹⁰⁰⁰⁰⁰⁰ 步 → 宇宙热寂了也算不完
注意指数的残忍：硬件进步完全追不上。电脑快 1000 倍，O(n²) 只能多处理约 30 倍的数据，而 O(log n) 几乎毫无压力。所以工程师说：「能用更好的算法，就不要堆硬件。」
大O还有个「抓大放小」的性格：只保留增长最快的那个部分。比如 3n² + 100n + 500，n 巨大时 n² 完全碾压后两项，于是记作 O(n²)。常数也不管——10n 和 100n 都是 O(n)，因为「增长形状」一样。
4
身边的真实例子
- 查通讯录：手机通讯录按拼音排好，你「二分」着翻——O(log n)。这就是数据库索引存在的意义。
- 排扑克牌：插牌排序是 O(n²)（每张都和手里牌比），高手用的归并思路是 O(n log n)——10 万张牌前者要几十年，后者几分钟。
- 快递派送：给 100 个包裹排最佳路线，如果穷举所有顺序，约是 O(n!)（比 O(2ⁿ) 还爆炸），所以导航 App 用「够好的近似算法」而不是「完美解」。
最后这个例子引出了计算机科学最著名的悬案——「P 与 NP 问题」：哪些问题能快速求解？哪些只能穷举？目前没人证明得了，悬赏百万美元。
?
常见疑问
O(log n) 的 log 底数重要吗？
不重要。大O忽略常数因子，而不同底数只差常数倍，所以一律简写 log n。理解成「每次砍一半」就够了。
O(n²) 一定比 O(n) 慢吗？
n 很大时一定。但数据量小（比如 n=10）时，O(n²) 的简单算法可能反而更快，因为「常数开销」小。所以工程师常说：数据规模决定算法选择。
大O里的「时间」和「空间」是两回事吗？
对，分别叫时间复杂度和空间复杂度。常见取舍：多花点内存（空间）换速度（时间），比如提前把结果存进表里（缓存/记忆化），用 O(n) 空间换回 O(log n) 甚至 O(1) 的查询。
→