输入规模与增长速度

复习

• 算法与正确性：算法是有限、明确、可执行的步骤
• 正确性：正确之外，还要关心它运行得有多快
• 数据结构：组织数据的方式会直接影响操作的代价

TL;DR

• 衡量算法快慢，要看运行时间随输入规模怎样变化
• 一次运行时间受机器和常数影响，不适合直接比较
• 规模小时差距不明显，规模大后趋势才决定一切
• 真正该关注的，是运行时间的增长速度

正文

　　上一章说，算法光正确还不够，还得跑得完。那要怎样衡量“快慢”？

　　最直接的想法是掐表：跑一次，看看花了多少毫秒。但这很快就行不通了——换台更快的电脑，数字就变了；换个输入，数字也变了；甚至运气好一点，结果都不同。用一组孤立的运行时间，说明不了算法的本质。

换个角度：看它怎样“长”

　　更靠谱的思路，是换个问法：当输入规模变大时，运行时间会怎样变化？

　　这里的“输入规模”，通常记作 n：要排序的元素个数、要查找的数据量、图里节点的数量……我们关心的不是某个具体 n 下花了几秒，而是 n 增长时，耗时按什么规律增长。

　　先看一个对比。假设有两个算法，处理的元素个数是 n：

　　规模小的时候，两者看着都还行。可当 n 从 1000 变成 2000：

• 算法甲的操作数只翻了一倍，从 1000 到 2000
• 算法乙却翻了四倍，从 100 万到 400 万

　　规模越大，增长速度的差距就越被放大，最终压倒一切。

常数救不了坏趋势

　　你可能会想：那我把算法乙用快 100 倍的机器跑，不就追上了？

　　追不上。因为“快 100 倍”只是一个常数上的优势，它让所有数据都除以 100，却改变不了增长的趋势。只要 n 一直变大，n² 迟早会把 100n 甩在身后。对足够大的 n，增长更慢的算法一定赢。

　　这也解释了为什么换一台更快的电脑，通常救不了一个设计糟糕的算法：机器提升的是常数，算法决定的才是趋势。

　　那么，该用什么工具来描述这个“趋势”呢？下一章，我们请出大 O 记号。

思考题 1

　　为什么“换一台快 100 倍的电脑”不能改变两个算法之间的优劣关系？

思考题 2

　　有没有可能：在小数据上 A 更快，在大数据上 B 更快？这说明了什么？

小结

知识点

• 用“随规模增长的趋势”衡量算法更本质
• 输入规模通常记作 n
• 增长速度的差距会随规模放大
• 常数因子无法改变增长趋势

参考资料

1. Wikipedia(zh)：算法分析：研究算法资源消耗随规模的变化
2. Wikipedia(zh)：时间复杂度：描述运行时间随输入规模的增长

思考题答案（仅供参考）

思考题 1

　　因为“快 100 倍”只是把所有时间除以同一个常数，改变不了增长趋势。增长更快的一方，在规模足够大时所需的操作数会超过增长更慢的一方乘以任何常数。常数优势只在小规模下可能起决定作用。

思考题 2

　　完全可能。小规模时，常数项、实现细节可能让 A 更快；但随着规模增大，增长更慢的一方（这里假设是 B）会反超。这说明比较算法要明确“在什么规模下”，也说明为什么我们更关心大规模下的增长趋势。

协议

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

封面图

设计师 | 南国微雪