
No.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)
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が見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
医師・看護師・助産師
薬剤師・登録販売者・MR
医療事務・調剤薬局事務
歯科衛生士・歯科助手
臨床検査技師・臨床工学技士
理学療法士・作業療法士・言語聴覚士
臨床心理士・心理カウンセラー・ソーシャルワーカー
介護福祉士・ケアマネージャー・社会福祉士
弁護士・行政書士・司法書士・社会保険労務士
フィナンシャルプランナー(FP)
中小企業診断士
公認会計士・税理士
簿記検定・漢字検定・秘書検定
情報処理技術者・Microsoft認定資格
TOEFL・TOEIC・英語検定
建築士
インテリアコーディネーター
宅地建物取引主任者(宅建)
不動産鑑定士・土地家屋調査士
マンション管理士
電気工事士
美容師・理容師
調理師・管理栄養士・パティシエ
シェフ
保育士・幼稚園教諭
教師・教員
国家公務員・地方公務員
警察官・消防士
その他(職業・資格)
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
10分の1は「10/1 それとも1/10...
-
0.1と0.10の違いを教えて下さい。
-
「最大300字程度」
-
1億x1億はいくらでしょうか?
-
50以下は“50”も入るのですか?
-
「充足に達しましたので」これ...
-
偏微分の記号をタイプするため...
-
100以下の自然数のうち、次のよ...
-
16進小数0.Cを10進数小数に変換...
-
5進法を10進法への直し方
-
【機械図面】 最大値・最小値...
-
実績を積むという表現
-
アクセスのデータ型。数値型に...
-
8ビットのグレイ符号10110110お...
-
エクセル関数で源泉徴収額を計...
-
言葉遣いについて ○○を取りに行...
-
HEX2BIN関数の使い方。
-
3桁の自然数の中で、次の個数を...
-
「じじょう」が正しい読み方?
-
dBm→dBμV/mの換算について
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
10分の1は「10/1 それとも1/10...
-
0.1と0.10の違いを教えて下さい。
-
故障率の算出方法
-
有効数字3桁 有効数字3桁で4桁...
-
これ、正解ですか?
-
四捨五入で桁が変わる場合の表...
-
MIPS値の計算
-
ド・モルガンの法則について
-
稼働率?利用率?の求め方
-
切り上げ 切捨て 四捨五入 の...
-
基本情報技術者の問題で・・・
-
解説お願いします。 m/n 冗長シ...
-
計算量のオーダについて
-
原価計算で・・・
-
トリップフリーって何ですか? ...
-
単なる理想値なのかも知れませ...
-
基本情報技術者試験の問題です...
-
逆ポーランド法の表記について
-
情報の問題です 装置Aと装置B...
-
血清浸透圧のついて
おすすめ情報