計算量のオーダについて

質問

Ｏ(n＾2+nlogn）
Ｏ(n√ｎ+nlogn）
Ｏ(nlogn+n^2）+Ｏ(（n＾1.67）logｎ）
Ｏ(nlogn+n^100）Ｏ(n＾0.7+logｎ）

この４つの式をそれぞれ簡略化せよという問題なのですが、
考え方がよくわかりません。
どなたかご教授よろしくお願いします。

回答No.1

jjon-com · ベストアンサー

http://ja.wikipedia.org/wiki/ランダウの記号 の「4 一般的なオーダー」
http://ja.wikipedia.org/wiki/対数 の「2.3 特殊な底」

を参照すると，計算量の世界では logｎという表記は慣例的に底＝２が省略されているとみなしてもよいのですね。

オーダの考え方については，下記URLの該当箇所を参照。
http://ja.wikipedia.org/wiki/ランダウの記号 の「1.1 無限大における漸近挙動」

私の数学力は logとは何かを知っている程度で抽象的に式を展開できないので，ｎに比較的大きな値を代入してみて，この項の方が大きく変化するだろうとイメージしてみただけです。数学に詳しい方がいらっしゃいましたら，間違いをぜひ指摘していただきたいです。私にとってもたいへん勉強になります。

(1) Ｏ(n＾2+nlogn）
例としてｎ＝100としてみる。
左項は 100×100
右項は 100×log2(100)≒100×log2(128)＝100×７
左項の影響が大きいので右項は無視できる。
【答】Ｏ(ｎ^2)

(2) Ｏ(n√ｎ+nlogn）
例としてｎ＝100としてみる。
左項は 100√100 ＝ 100×10
右項は 100×log2(100)≒100×log2(128)＝100×７
左項の影響が大きいので右項は無視できる。
【答】Ｏ(ｎ√ｎ)

(3) Ｏ(nlogn+n^2）+Ｏ(（n＾1.67）logｎ）
例としてｎ＝100としてみる。
左のオーダ式は(1)より Ｏ(ｎ^2)，よって100×100＝10,000
右のオーダ式は(100^1.67)×log2(100)≒2188×log2(128)≒15,314
右のオーダ式の影響が大きいので左のオーダ式は無視できる。
【答】Ｏ((ｎ^1.67)×logｎ)

(4) Ｏ(nlogn+n^100）Ｏ(n＾0.7+logｎ）
左のオーダ式は(1)より Ｏ(ｎ^100)
例としてｎ＝100としてみる。
右のオーダ式の左項は 100^0.7≒25
右のオーダ式の右項は log2(100)≒log2(128)＝７
左項の影響が大きいので右のオーダ式は Ｏ(ｎ^0.7)
全体では Ｏ(ｎ^100)×Ｏ(ｎ^0.7) なので
【答】Ｏ(ｎ^100.7)

お礼

詳しい説明ありがとうございました！