トップダウンマージソートの最良のケースの時間計算量がO(nlogn)にあるのはなぜですか? トップダウン マージ ソートの最良のケースは 1 だと思います。1 回だけ比較する必要があります。最悪の場合、最良の場合、平均的な場合のボトムアップ マージ ソートの時間計算量はどうですか。
もう 1 つの質問は、各反復が正確に O(n) かかる理由です。誰かがそれを助けることができますか？
質問する
17458 次
1 に答える
5
トップダウンマージソートの最良のケースの時間計算量がO(nlogn)にあるのはなぜですか?
各反復で、配列を 2 つのサブリストに分割し、アルゴリズムを再帰的に呼び出すためです。せいぜい、それを正確に半分に分割することで、(各再帰呼び出しの問題を) 元の問題の半分に減らすことができます。log_2(n) 回の反復が必要であり、各反復には正確に時間がかかりますO(n)(各反復はすべてのサブリストにあり、合計サイズはまだ ですn) O(nlogn)。
ただし、リストが既にソートされているかどうかを確認する簡単な前処理を行うと、O(n).
リストがソートされているかどうかのチェックはそれ自体O(n)であるため、 では実行できませんO(1)。「最良のケース」は一般的な「最良のケース」でnあり、特定のサイズではないことに注意してください。
最悪の場合、最良の場合、平均的な場合のボトムアップ マージ ソートの時間計算量はどうですか。
同じアプローチで、O(n) ベスト ケースからボトムアップ (単純な前処理) を得ることができます。ボトムアップ マージ ソートの最悪のケースと最良のケースはO(nlogn)次のとおりです。このアプローチでは、リストは常に 2 つの等しい長さ (差 1 まで) のリストに分割されるためです。
于 2012-10-12T10:33:22.903 に答える