algorithm - O(n^2) 対 O (n(logn)^2)

Question

時間の複雑さはO(n^2)それよりもO (n(logn)^2)優れていますか?

単純化すると、

O(n) vs O((logn)^2)

とlogn< n、しかしどうlogn^2ですか？

score 18 · Accepted Answer

nの値が0.49 未満の場合、 nは( log n) ^{2未満です...}

したがって、一般に( log n) ²はnが大きい場合に適しています ...

しかし、これらのO (何か)表記は常に定数要素を除外するため、あなたの場合、どちらのアルゴリズムが優れているかを確実に言うことはできないかもしれません...

グラフは次のとおりです。

ここに画像の説明を入力

(青い線はn、緑の線は( log n) ² )

nの値が小さい場合の差はそれほど大きくなく、Big-O 表記に含まれていない定数係数によって簡単に小さくなってしまうことに注意してください。

しかし、 nが大きい場合は( log n) ²が勝ちます:

ここに画像の説明を入力

score 13 · Accepted Answer

各定数について、k漸近的log(n)^k < nに .

証明は簡単です。方程式の両辺をログに記録すると、次のようになります。

log(log(n))*k < log(n)

漸近的に、これが正しいことは簡単にわかります。

意味上の注意: ここではlog(n)^k == log(n) * log(n) * ... * log(n) (k times)、NOTと仮定しますlog(log(log(...log(n)))..) (k times)。使用されることもあります。

score 3 · Accepted Answer

O(n^2) vs. O(n*log(n)^2)
<=> O(n) vs. O(log(n)^2) (divide by n)
<=> O(sqrt(n)) vs. O(log(n)) (square root)
<=> polynomial vs. logarithmic

対数が勝ちます。

score 0 · Accepted Answer

(logn)^2も＜nです。

例を見てみましょう:

 n = 5
 log n = 0.6989....
 (log n)^ 2 = 0.4885..

ご覧のとおり、(long n)^2 はさらに縮小されています。

n の値が 100,000,000 のように大きくても、

   log n = 9
   (log n)^ 2 = 81

これはよりはるかに少ないですn。

score 0 · Accepted Answer

(Log n)^2 の方が優れています。なぜなら、変数の変更 n を exp m で行う場合、m^2 は exp m よりも優れているからです。

score -1 · Accepted Answer

O(n(logn)^2) は、n が大きい場合に優れています (高速です)。

両側からログを取る:

ログ(n^2)=2ログ(n)

Log(n(logn)^2)=Log(n)+2log(Log(n))=Log(n)+2log(Log(n))

lim n--> 無限 [(Log(n)+2log(Log(n)))/2log(n)/]=0.5 (ロピタルのルールを使用)(http://en.wikipedia.org/wiki/ L'H%C3%B4pital's_rule)]

6 に答える 6