No.1ベストアンサー
- 回答日時:
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で質問しましょう!
似たような質問が見つかりました
- 数学 O(N*logN)よりN=8の時、 O(N*logN) のOはオーダー記号と推察されますから 8*l 6 2022/04/06 18:54
- 数学 (2)が分かりません。 Imfの基底は行基本変形で求めることって出来ますよね? ここからImfの基底 1 2023/06/04 16:14
- 統計学 ガチャガチャの中に、あるアニメの キャラAのフィギュアが3種類1個ずつ キャラBのフィギュアが3種類 1 2022/06/04 15:28
- 数学 数学の問題の解説お願いします! 4 2022/08/28 05:22
- Excel(エクセル) コストカットについて質問です。 添付画像の総コスト・総教育コスト・総思考コストの計算をしたいのですが 5 2022/12/21 16:10
- 数学 情報処理詳しい人!! A4縦のレポート文書に4:3の大きさの横向きの写真画像を貼り付けることにした。 2 2022/12/18 02:30
- 会計ソフト・業務用ソフト Excel IF構文内の計算式を有効にする方法 2 2023/03/22 11:27
- 大学受験 高校数学の順列の問題です。 男4人、女4人の計8人について、つぎのような並び方はそれぞれ何通りあるか 3 2023/06/01 16:52
- 化学 200ulの1MのNaOHを作り方を教えてください 1 2022/11/09 22:25
- 数学 虚数単位:i、この4乗根を求める解答したものの疑問です。 1 2022/10/25 00:43
このQ&Aを見た人はこんなQ&Aも見ています
-
新NISA制度は今までと何が変わる?非課税枠の拡大や投資対象の変更などを解説!
少額から投資を行う人のための非課税制度であるNISAが、2024年に改正される。おすすめの銘柄や投資額の目安について教えてもらった。
-
O(n log n)について2
C言語・C++・C#
-
整列の比較回数を表す数式でよく見るO(n log n)のOって何ですか
その他(データベース)
-
テスターの周波数特性について
その他(自然科学)
-
-
4
トランジスタ増幅回路の入出力特性の歪みについて
その他(教育・科学・学問)
-
5
エミッタ接地増幅回路について教えてください><
物理学
-
6
「水素のイオン化エネルギーは13.6eVである。水素の原子核と電子の間に働く力がクーロン力だけである
物理学
関連するカテゴリからQ&Aを探す
医師・看護師・助産師
薬剤師・登録販売者・MR
医療事務・調剤薬局事務
歯科衛生士・歯科助手
臨床検査技師・臨床工学技士
理学療法士・作業療法士・言語聴覚士
臨床心理士・心理カウンセラー・ソーシャルワーカー
介護福祉士・ケアマネージャー・社会福祉士
弁護士・行政書士・司法書士・社会保険労務士
フィナンシャルプランナー(FP)
中小企業診断士
公認会計士・税理士
簿記検定・漢字検定・秘書検定
情報処理技術者・Microsoft認定資格
TOEFL・TOEIC・英語検定
建築士
インテリアコーディネーター
宅地建物取引主任者(宅建)
不動産鑑定士・土地家屋調査士
マンション管理士
電気工事士
美容師・理容師
調理師・管理栄養士・パティシエ
シェフ
保育士・幼稚園教諭
教師・教員
国家公務員・地方公務員
警察官・消防士
その他(職業・資格)
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
10分の1は「10/1 それとも1/10...
-
故障率の算出方法
-
解説お願いします。 m/n 冗長シ...
-
0.1と0.10の違いを教えて下さい。
-
計算量のオーダについて
-
情報の問題です 装置Aと装置B...
-
有効数字3桁 有効数字3桁で4桁...
-
稼働率?利用率?の求め方
-
基本情報技術者試験の問題です...
-
1億x1億はいくらでしょうか?
-
5進法を10進法への直し方
-
50以下は“50”も入るのですか?
-
実績を積むという表現
-
エクセル関数で源泉徴収額を計...
-
【機械図面】 最大値・最小値...
-
100以下の自然数のうち、次のよ...
-
「最大300字程度」
-
エクセルで60進法計算の仕方...
-
敬語の使い方
-
16進小数0.Cを10進数小数に変換...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
おすすめ情報