常见增长速度

复习

• 大 O 记号：大 O 描述增长速度的数量级
• 渐近比较：只保留最高阶项，忽略常数与低阶项
• 增长趋势：它描述的是趋势，不是精确耗时

TL;DR

• 常见增长速度有：常数、对数、线性、线性对数、平方、指数
• 它们之间的差距会随规模急剧拉大
• 对数增长极慢，平方和指数增长极快
• 记住数量级直觉，比死记公式更有用

正文

　　有了大 O，我们就可以把算法按增长速度分门别类。常见的几档，从慢到快大致是这样：

对数：砍半的威力

　　先说最容易被低估的 O(log n)。它的经典代表是二分查找：每次比较都能排除掉一半的数据。

　　这意味着，数据量翻倍，只多花一步。从 1000 个数里找，约需 10 次；从 100 万个数里找，也只要约 20 次。指数级增长的规模，换来的是线性增长的步数——这就是对数的神奇之处。

线性与平方

　　O(n) 很直观：挨个看一遍，数据翻倍，时间翻倍。这通常已经相当不错了。

　　而 O(n²) 往往来自“两层循环”这种结构：外层每走一步，内层都要把数据过一遍。规模翻倍，内层和外层各自翻倍，合起来就是四倍。数据一多，它很快会变得难以忍受。

指数：能不用就别用

　　O(2ⁿ) 更糟。像“枚举所有子集”这类做法，每多一个元素，要处理的可能性就翻一倍。

　　感受一下这个差距：同样处理 n = 1000，

• O(n) 大约是 1000 次操作
• O(n²) 是 100 万次，还能忍
• O(2¹⁰⁰⁰) 则是个比宇宙原子总数还大的天文数字，无论如何也跑不完

　　所以，算法设计的很大一部分努力，就是想办法避开指数级，把问题拉回多项式级别。后面讲的动态规划、贪心等技巧，很多都在做这件事。

　　另外提醒一句：这些记号描述的是随着 n 增长的趋势。在 n 很小时，O(n²) 甚至可能比 O(log n) 更快，因为常数更小。规模不够大时，别急着下结论。

思考题 1

　　为什么二分查找是对数级，而逐个检查是线性级？

思考题 2

　　当 n 从 1000 增到 2000 时，线性、平方、指数三种算法的时间大致各自怎样变化？

小结

知识点

• 常见增长速度：常数、对数、线性、线性对数、平方、指数
• 对数增长极慢，平方与指数增长极快
• 二分查找是 O(log n) 的典型代表
• 避开指数级是算法设计的重要目标

参考资料

1. Wikipedia(zh)：时间复杂度：各种常见增长量级
2. Wikipedia(zh)：二分查找算法：每次排除一半的对数级查找

思考题答案（仅供参考）

思考题 1

　　逐个检查每次都只排除一个元素，要看完全部 n 个才确定，所以是线性级。二分查找每次比较都能排除一半，问题的规模不断除以 2，从 n 到 1 只需要约 log₂n 步，所以是对数级。

思考题 2

　　线性算法大约翻倍；平方算法大约变四倍；指数算法则从 2¹⁰⁰⁰ 变成 2²⁰⁰⁰，相当于又自乘了一次，增长得极其可怕。规模越增大，三者的差距越夸张。

协议

　　本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

封面图

设计师 | 南国微雪