ここから質問投稿すると、最大4000ポイント当たる!!!! >>

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

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

A 回答 (1件)

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


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

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


人気Q&Aランキング