数据结构：时间成本，大O符号

对于大尺寸的问题，随着时间的算法成本O(2^n)比的算法已经时间成本O(N^2)数据结构：时间成本，大O符号

这是真的还是假的更快？我认为如果C^n，C =常数且C> 1，那么它的增长速度将快于O（N^2）。它是否正确？

来源

2012-12-11 hibc

对于较大的问题的大小，与时间成本O（2 ^Ñ）比具有时间成本为O（n 2 ）的算法更快的算法。

FALSE，因为2 ^Ñ>Ñ对于n> 4，和更大的手段慢。

对于C =常数，C> 1，C ^Ñ生长为O更快（N ）。

TRUE。

Here是Wolfram | Alpha参考。

enter image description here

来源

2012-12-11 06:26:56

非常感谢。所以2^N大于N^2，这意味着N^2更快？我认为更好的手段更快.. – hibc

@hibc正确，因为_cost_不是一个伟大的词^ _- –

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

来源

2012-12-11 06:06:27

把参考资料或给更多的细节。 –

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-11 06:27:53

d/dn c^n = c^n * log（c），所以它应该是c^n * lg^2 （c）/ 2 - > inf –

是的，我的意思是，而不是c^n lg（n lg n）对不起，我很困惑 –

这显然是错误的。你可以通过试验和错误的不同值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-11 06:44:37 tskuzzy

非常感谢！所以更大的价值意味着时间成本要慢得多。我是否明白了吗？ – hibc

那么你说的功能代表“时间成本”是的。更大的时间成本意味着更慢的执行（按定义）。 – tskuzzy

数据结构：时间成本，大O符号

回答

相关问题