big-o - O(n Log n) は多項式時間ですか?

Question

O(n Log n) は多項式時間ですか? もしそうなら、その理由を説明していただけますか？

私は数学的な証明に興味がありますが、強い直感にも感謝します。

ありがとう！

Answer 1

はい、O(nlogn) は多項式時間です。

http://mathworld.wolfram.com/PolynomialTime.htmlから、

与えられた入力に対してアルゴリズムを完了するのに必要なステップ数が非負の整数 m に対して O(n^m) である場合、アルゴリズムは多項式時間で解けると言われます。ここで、n は入力の複雑さです。

http://en.wikipedia.org/wiki/Big_O_notationから、

f は O(g) iff

ここで、ある m に対して n log n が O(n^m) であることを証明します。これは、n log n が多項式時間であることを意味します。

確かに、m=2 を取ります。(これは、n log n が O(n^2) であることを証明することを意味します)

証明のために、k=2 を取ります。(これはもっと小さくてもかまいませんが、そうである必要はありません。) より大きなすべての n に対して次が成立するような n_0 が存在します。

n_0 * f(n) <= g(n) * k

n_0 = 1 とします (これで十分です)

n ログ n <= 2n*n

ログ n <= 2n

n > 0 (仮定)

よくわからない場合は、ここをクリックしてください。

この証明は、latex 数学モードの方がはるかに優れている可能性がありますが、stackoverflow がそれをサポートしているとは思いません。

Answer 2

これは、多項式 (n) によって上限があるためです。グラフを見てそこから先に進むこともできますが、それ以外の数学的証明を定式化することはできません:P

編集:ウィキペディアのページから、「アルゴリズムの入力のサイズの多項式式によって実行時間が上限に制限されている場合、アルゴリズムは多項式時間であると言われます」。

Answer 3

少なくとも多項式時間より悪くはありません。それでも良くない: n < n log n < n*n.

Answer 4

はい。n が無限大になるときの nlogn の限界は何ですか? 直観的に、大きな n の場合、n >> logn であり、積が n によって支配されていると見なすことができるため、nlogn ~ n であり、これは明らかに多項式時間です。より厳密な証明は、Inspired が行ったサンドイッチ定理を使用することです。

n^1 < nlogn < n^2.

したがって、 nlogn は、多項式時間であるシーケンスによって上 (および下) に制限されます。