Quicksort の実装をテストしているときに問題が発生しました。中央値などの数値をピボットとして選択すると、アルゴリズムがより適切に機能すると言われましたが、私の結果は期待したものではありません。通常、最初または最後の要素のいずれかをピボットとして選択すると、最良のシナリオが発生します。これらは両方とも、配列内の他のすべての要素と同様に乱数です。多くのテスト (5000 以上) を実行し、平均時間をチェックしています (最頻値や中央値を探す時間はありません)。ありがとうございました。
1 に答える
2
配列の中央値またはモードの計算はコストのかかる操作 (特に中央値の選択) であるため、適切なピボットが得られたとしても、それらのピボットを見つけるための追加のオーバーヘッドが、おそらく効率の向上のほとんどを食い尽くします。
ランダム化されたクイックソート (毎回ランダムなピボットを選択する) は、実際にははるかに優れた選択肢になります。その最悪のケースは指数関数的に起こりそうになく、期待どおりに時間 O(n log n) で実行されます。また、配列の中央値またはモードを見つけるよりも、乱数または疑似乱数を生成する方がはるかに高速です。
最後に、配列のモードを選択した場合、適切なピボットが得られるという保証はまったくありません。実際、重複のない配列があり、モードを選択する実装が常に最小値または最大値を選択する場合、これは病的なケースにつながる可能性があります。それは Θ(n 2 ) 時間に縮退します。
お役に立てれば！
于 2013-10-30T19:13:59.253 に答える