我认为这里的一部分混乱源于算法没有"大O"或"大-Theta" 的事实.O和Θ表示法用于描述函数的长期增长率,而不是算法.当你听到有人说"二进制搜索是O(log n)"之类的东西时,他们真正说的是"二进制搜索的运行时是O(log n)"或"二进制搜索的最坏情况运行时".长度为n的输入为O(log n)."
这可能令人困惑的另一个原因是一个函数可以是许多不同函数的大O. 例如,函数f(n)= n是O(n),但它也是O(n 2),O(n 3),O(2 n)等.这源于big-O的形式定义符号,表示f(n)= O(g(n))如果(直观地)长期f(n)从上面以g(n)的某个常数倍为界.这意味着我们不一定能说出某个函数运行时的"大"O,因为可能存在无限多的函数可能适合该法案.
我们可以说如下:如果函数的运行时是Θ(f(n)),那么函数的运行时也是O(f(n)).这是从Θ符号的定义得出的.另一方面,反过来不一定是真的; 如果函数具有运行时O(f(n)),则不一定是函数的运行时为Θ(f(n))的情况.我们可以使用像二进制搜索这样的例子 - 二进制搜索在时间O(log n)中运行,但它的运行时也是O(n)和O(n 2),因为它们是较弱的边界.然而,二分搜索的运行时间不是Θ(n),也不是Θ(n 2)或Θ(2 n).
| 归档时间： |
|
| 查看次数： |
683 次 |
| 最近记录： |