algorithm - データ構造：時間コスト、BigO表記

Question

問題のサイズが大きい場合、時間コストのあるアルゴリズムは、時間コストO(2^n)のあるアルゴリズムよりも高速です。O(N^2)

これは本当ですか、それとも間違っていますか？

私が思うに、C ^ n、C =定数、C> 1の場合、O（N ^ 2）よりも速く成長します。これは正しいです？

Answer 1

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 の成長が遅くなると言えます。

Answer 2

それは明らかに誤りです。のさまざまな値を試行錯誤することで、これを納得させることができますN。

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

ご覧のとおり、指数関数は二次関数よりもはるかに速く成長します。

この主張を証明するために、 の基本ケースで帰納法を使用しN=5ます。この手順は、読者への演習として残されています。

Answer 3

問題のサイズが大きい場合、時間コストが O(2 ^{n ) のアルゴリズムは、時間コストが O(n 2} )のアルゴリズムよりも高速です。

FALSE 。 n > 4 の場合は 2 ⁿ > n ²であり、それ以上は低速であることを意味します。

C = 一定で C > 1 の場合、C ^{nは O(n 2} )よりも速く成長します。

真。

これはWolfram |Alpha リファレンスです。

Answer 4

はい、c^n は n^2 よりも速く成長します。