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ですか？

Answer 1

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

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

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

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

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

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

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

Answer 2

各定数について、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)。使用されることもあります。

Answer 3

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

対数が勝ちます。

Answer 4

(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。

Answer 5

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

Answer 6

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)]