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

A 回答 (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)
    • good
    • 0
この回答へのお礼

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

お礼日時:2008/05/07 19:05

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

今、見られている記事はコレ!

  • 初めての婚活で異性にウケず自信喪失……

    連日のように至るところで開催されている婚活パーティ。参加したものの、不甲斐ない結果(?)にショックを受ける人もいるようだ。今回は「教えて!goo」に寄せられた婚活に関する相談「初めての婚活で自信を失いま...

  • ゲーム業界ダンナ観察日記:第85話「経験値を手に入れろ」

    ダンナ様のねむねむ。奥様のとぽすけ。ごく普通のふたりは、ごく普通の結婚をし、だらだらと夫婦生活を送っていました。でもただひとつ違っていたのは、ダンナ様はゲーム会社勤務だったのです。

  • ナウなヤングに通じません:第4話「それな」

    同じ日本語なのに全く会話が噛み合ない…。流行言葉に追いつけない死語ライターのおじちゃんと姪っ子ちゃんの、ハート古ジェネレーションギャップギャグ漫画です。

  • 東京の水はまずい?地方民が悩む「カップ麺は水道水でOK?」

    水には味がある。といって、もしピンと来ない人がいるならば、おそらくは水道水が美味しい地域で育った人かもしれない。ことに都市部では「水道水がまずい」という声はよく聞かれるものだ。 「教えて!goo」で「東...

  • 製氷皿で簡単!コロコロフルーツ寒天

    氷を作る「製氷皿」を使った意外な利用法やレシピが話題になっている。「教えて!goo」でも「氷を作るだけじゃない!?暮らしに役立つ製氷皿の便利な使い方」や「【自宅で簡単】100均製氷皿を使ってお寿司を量産してみ...

おしトピ編集部からのゆる~い質問を出題中

お題をもっとみる

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


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ