0

对于大型问题，具有时间成本O(2^n)的算法比具有时间成本的算法快O(N^2)

这是对还是错？

我认为如果 C^n, C = constant 并且 C > 1，那么它的增长速度会比 O(N^2) 快。它是否正确？

4

4 回答 4

2 
Yes, c^n grows faster than n^2, if c>1
if c=1 then c^n =1
if c<1 then c^n "decays"

Proof for c>1
let t(n) = (c^n)/(n^2)
now lim n-> infinity t(n) = (By L'Hospitals Rule) = lim (d/dn c^n) / lim(d/dn n^2)
= lim (d/dn c^n lg n) / lim(d/dn 2n)    
= lim (d/dn c^n lg n * lg n) / lim(d/dn 2)
-> infinity.

因此，根据http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations中描述的属性，我们说 n^2 增长较慢。

于 2012-12-11T06:27:53.133 回答
1

对于大型问题，时间成本为 O(2 n ) 的算法比时间成本为 O(n 2 ) 的算法快。

FALSE，因为 2 n > n 2表示 n > 4，更大意味着更慢。

对于 C = 常数且 C > 1，C n的增长速度快于 O(n 2 )。

真的。

这是 Wolfram|Alpha 参考。

在此处输入图像描述

于 2012-12-11T06:26:56.080 回答
1

这显然是错误的。您可以通过对不同值的反复试验来说服自己相信这一点N。

2^5 = 32 versus 5^2 = 25
2^6 = 64 versus 6^2 = 36
2^7 = 128 versus 7^2 = 49

如您所见，指数的增长速度比二次的快得多。

为了证明这一说法，我将使用归纳法和基本情况N=5。这一步留给读者作为练习。

于 2012-12-11T06:44:37.830 回答
0

是的，c^n 比 n^2 增长得更快。

于 2012-12-11T06:06:27.683 回答