渐近分析

渐近分析是这样一种做法：评判一个算法，看的是当输入规模趋向无穷时它的代价如何变化，而不是某一个具体输入下精确的步数。「渐近」不过是「越走越远」的意思。它背后的洞见是：对小输入来说，几乎什么都够快——真正决定现实成败的差距，只有当 n 很大时才显现出来。所以我们故意拉远镜头，去研究趋势，而不是那一个点。正是这种推理，产出了「归并排序是 O(n log n)」「冒泡排序是 O(n^2)」这样的论断。

这样一来，分析既更简单也更诚实。因为我们只关心大 n 下的行为，我们就有理由丢掉常数因子和低阶项——这正是大 O 所编码进去的那条简化。我们不说「这在我笔记本上要花 4n + 7 微秒」，因为这个数字很脆弱：更快的 CPU、更好的编译器、不同的语言都会改变它，可它们当中没有一个能改变代价究竟是像 n 那样长还是像 n^2 那样长。把这些机器相关的噪声扔掉，渐近分析就分离出了一个算法身上真正属于算法本身的那一部分。

它有三种值得记住的口味。大 O（O）给出上界——增长不会比这更糟。大 Omega 给出下界——不会比这更好。大 Theta 把它夹在两者之间——一个紧界。我们还区分最好、平均、最坏情况：快速排序平均是 O(n log n)，可在它的最坏情况下是 O(n^2)。正是渐近分析这门功夫，让两个工程师能在白板上比较设计——远在任何一个人写下一行代码之前——并就「哪一个能随规模扩展」达成一致。