《算法导论（原书第3版）》一第3章 函数的增长

第2章中定义的算法运行时间的增长量级简单地刻画了算法效率，并且还允许我们比较可选算法的相对性能。一旦输入规模n变得足够大，最坏情况运行时间为Θ(nlgn)的归并排序将战胜最坏情况运行时间为Θ(n2)的插入排序。正如我们在第2章中对插入排序所做的，虽然有时我们能够确定一个算法的精确运行时间，但是通常并不值得花力气来计算它以获得多余的精度。对于足够大的输入，精确运行时间中的倍增常量和低阶项被输入规模本身的影响所支配。

当输入规模足够大，使得只有运行时间的增长量级有关时，我们要研究算法的渐近效率。也就是说，我们关心当输入规模无限增加时，在极限中，算法的运行时间如何随着输入规模的变大而增加。通常，渐近地更有效的某个算法对除很小的输入外的所有情况将是最好的选择。

本章给出几种标准方法来简化算法的渐近分析。下一节首先定义几类“渐近记号”，其中，我们已经见过的一个例子是Θ记号。然后，我们给出贯穿本书使用的几种记号约定。最后，我们回顾一下在算法分析中常见的若干函数的行为。