渐近表示法中的函数

当使用渐近符号表示算法运行时间关于输入规模$n$‍的增长速率时，有些事情需要记住。

让我们从一些简单的事情开始。假设一个算法需要常量时间，而不考虑输入大小。例如，如果为您提供了一个已按升序排序的数组，而您必须找到最小元素，则只需要常量时间，因为最小元素必须位于索引0。由于我们喜欢在渐近表示法中使用$n$‍的函数， 所以可以说此算法以$\mathrm{\Theta }(n^0)$‍时间运行。为什么？因为$n^0=1$‍，并且算法的运行时间的常数系数为1。在实践中， 我们不写$\mathrm{\Theta }(n^0)$‍，而写作$\mathrm{\Theta }(1)$‍。

假设一个算法需要 $\mathrm{\Theta }({\log }_{10}n)$‍ 的运行时间。你也可以说，它需要$\mathrm{\Theta }({\log }_{2}n)$‍的运行时间。当对数的底是一个常数时，这个常数是什么对于渐近表示法来说并不重要。 为何？有一个数学公式表明：

对于所有正数$a$‍、 $b$‍、$n$‍，如果$a$‍ 、 $b$‍ 是常数，则${\log }_{a}n$‍ 和 ${\log }_{b}n$‍ 只差一个系数${\log }_{b}a$‍，而这个系数是一个常量，我们在使用渐近表示法的时候可以忽略它。

因此，我们可以说最坏情况下的二分搜索的运行时间是$\mathrm{\Theta }({\log }_{a}n)$‍，$a$‍是任何正数。为什么？猜测次数最多是${\log }_{2}n+1$‍，每一次猜测和验证都需要常量时间，启动和返回结果也需要常量时间。然而，在实际应用中，我们经常说二分搜索需要的运行时间是$\mathrm{\Theta }({\log }_{2}n)$‍，因为计算机科学家更喜欢用2的幂来描述问题。

这是一个我们在使用渐近表示法时常常看见的函数顺序。如果$a$‍ 和 $b$‍ 是常数，且$a<b$‍， 则运行时间$\mathrm{\Theta }(n^a)$‍比运行时间$\mathrm{\Theta }(n^b)$‍增长更慢。例如运行时间$\mathrm{\Theta }(n)$‍，即$\mathrm{\Theta }(n^1)$‍，比运行时间$\mathrm{\Theta }(n^2)$‍增长更慢。这个指数不需是整数。例如，运行时间$\mathrm{\Theta }(n^2)$‍比运行时间$\mathrm{\Theta }(n^2\sqrt{n})$‍（即$\mathrm{\Theta }(n^{2.5})$‍）增长更慢。

下图比较了$n$‍、$n^2$‍、$n^{2.5}$‍的增长：

对数比多项式增长更慢。也就是说，$\mathrm{\Theta }({\log }_{2}n)$‍ 比关于 任何 正常量 $a$‍的 $\mathrm{\Theta }(n^a)$‍的增长更慢。但是， 由于 ${\log }_{2}n$‍的值随$n$‍ 的增加而增加，则$\mathrm{\Theta }({\log }_{2}n)$‍比$\mathrm{\Theta }(1)$‍增长更快。

下图比较了$1$‍、 $n$‍、 ${\log }_{2}n$‍的增长：

下面列出了渐近表示法中的函数列表，我们在分析算法时经常会遇到这些函数， 按最慢到增长最快的速度排序：

请注意，指数函数$a^n$‍ （其中 $a>1$‍）的增长速度快于任何多项式函数$n^b$‍， 其中 $b$‍ 是任何常量。

上面的列表并没有一一穷举，尚有许多函数的运行时间没有列出。希望你能在你的计算机科学的旅程中遇到一些这样的问题。

本内容是 达特茅斯计算机科学 教授 Thomas Cormen 和 Devin Balkcom，与可汗学院的计算课程团队合作完成。内容获得许可 CC-BY-NC-SA。