O(n ^ 3)真的比O(2 ^ n)更有效吗？
coy*_*ote -5 algorithm big-o asymptotic-complexity
我的算法类的作业声称O(n 3)比O(2 n)更有效.
当我将这些函数放入图形计算器时,对于非常大的n(从n = 982左右开始),f(x)= 2 x似乎始终更有效.
考虑到对于函数f(n)= O(g(n)),对于大于某个n 0的所有n,它必须更小,这不意味着从n = 982我们可以说O(2 n)效率更高？
2^n增长速度超过n^3.也许你已经在计算器中输入了错误的值或类似的东西.还要注意的是更有效的装置,更短的时间,这意味着一个较低的值上y-axis.
让我向您展示一些正确的图表(使用Wolfram Alpha):
首先 2^n是较小的(但只是一个很小的范围),之后你可以看到2^n它是如何增长的.
在这个交叉点之后,情况再也不会改变,并且2^n仍然非常大n^3.这也适用于你分析的范围,所以> 982,就像在下一个情节中看到的那样(n^3附近的情节x-axis):
另请注意,在Big-O-Notation中,我们总是根据功能的增长来比较功能.这就是为什么类似的东西O(n^3)不包含函数f : f(x) <= n^3,而是f : f(x) <= C * n^3在哪里C是一个任意常量,它可能很大,它可能很小.这说明了比较中的增长因素.还要注意,允许条件不能保持有限的数量x但是必须存在一些约束x'条件的位置,因此对于每个条件x > x'.
将此解释与维基百科的完整数学定义进行C比较k,其中is ,xis n和x'is n_0:
如果为真,f(n)则定义集合中的内容O(g(n)).
- 作为一个注释,我想补充一点,这个隐藏的常数因子`C`可能是为什么运行在'O(2 ^ n)`的算法确实可能比实际范围的输入更快的原因.为O(n ^ 3)`.可能是第二种算法具有极端开销,隐藏常数为"C = 1_000_000"或非常大.然而,"O-Notation"意味着:*"在某些时候,输入变得非常大,`O(2 ^ n)`将慢于'O(n ^ 3)`"*.但同样,如上所述,对于较小的输入,其他算法可能运行得更快,这些输入也可能完全是**相关的输入**. (2认同)