都道府県穴埋めゲーム

マージソートの演算回数について

締切済

  • 質問者：tugu17
  • 質問日時：
  • 回答数：1件

授業でマージソートはn個の入力に対して、分割にかかる演算回数はlog n(底は2)であると言っていたのですが、どうしてなるかがどうしてもわかりません。

どなたかわかるかた、よろしくお願いします。

通報する

この質問への回答は締め切られました。

質問の本文を隠す

A 回答 (1件)

No.1

  • 回答者： Tacosan
  • 回答日時：

「分割にかかる演算回数」の意味がよくわからないんですが, マージソートの解析の中で, 「時間」の項に log n が出てくることは基本的にないはず. あの解析は非常に単純に書くと


・log n 段の再帰があって
・各段で O(n) 時間の処理があるから
・全体で log n × O(n) = O(n log n)
という流れのはずです.
    • good
    • 0
    • 件
通報する

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

Q質問する（無料）

ページトップページトップ

Q質問する（無料）

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

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

おすすめ情報