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