質問

O(n^2+nlogn)
O(n√n+nlogn)
O(nlogn+n^2)+O((n^1.67)logn)
O(nlogn+n^100)O(n^0.7+logn)

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

通報する

回答 (1件)

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

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

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

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

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

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

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

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

この回答へのお礼

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

このQ&Aは役に立ちましたか?3 件

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

新しく質問する

注目の記事

おしトピアプリ登場記念!コメントで最大1万円分のギフト券があたる!

話題のトピックにさくっとコメントできる「おしトピ」にAndroid版アプリに続きiPhoneアプリも登場! どちらかのアプリをダウンロードして指定のオーダーにコメントした方に抽選で最大1万分のアマゾンギフト券をプレゼント! フジテレビ出身のフリーアナウンサー長谷川豊氏の質問にも回答受付中!

このQ&Aを見た人が検索しているワード


新しく質問する

毎日見よう!教えて!gooトゥディ