渐近分析

函数增长

在比较算法性能时，虽然有时我们能够确定一个算法的精确运行时间，但是通常并不值得花力气来计算它（精度多余了）。对于足够大的输入，算法的运行时间中的常数倍数和低阶项相对于输入规模的影响变得不那么显著。

因此，我们研究渐近效率。我们关心：当输入规模无限增加时，在极限中，算法的运行时间如何随着输入规模的变大而增加。

---

渐近记号

以下是常用的渐近记号。

对于两个函数f、g的渐近比较，我们可以将其类比成实数a、b的比较。