4

常に中央値要素をピボットとして選択しない理由がよくわかりません。これは O(n) で実行できるため、総実行時間は O(n log n) になります。

おそらく、中央値検索の O(n) に大きな定数が隠されていると思います。

4

3 に答える 3

7

ウィキペディアのクイックソートページから：

逆に、最悪の場合の選択アルゴリズムが利用可能であることがわかったら、それを使用してクイックソートのすべてのステップで理想的なピボット（中央値）を見つけ、最悪の場合のO（n log n）実行時間のバリアントを生成できます。ただし、実際の実装では、このバリアントは平均してかなり低速です。

言い換えれば、O（n log n）が保証されるように強制するコストは、一般的に支払う価値がありません。そのページと選択アルゴリズムのページに詳細があります。

于 2011-03-31T06:33:50.913 に答える
0

ランダム化されたクイックソートを使用すると、非常に高い確率で最悪の実行時間が O(n log n) になります。

于 2011-03-31T14:47:36.457 に答える
0

どうやら中央値を見つけるための実行時間は、パーティションのランダム化されたバージョンを使用すると O(n) のように見えますが、実際には、パーティションが再び極端に不均衡になると、実行時間は O(n 2 ) になります。したがって、ここからすぐに改善することはできません。しかし、まだ希望があります。「CORMEN」を実行すると、最悪のシナリオでも線形時間で i 次の統計を見つけることができることがわかります。使用される手法は、中央値の中央値をピボット要素として使用し、いずれの場合でも線形実行時間を保証するネディアンを見つけることです。そのため、クイックソートでその手法を使用して、O(nlgn) の実行時間を取得することもできます

于 2012-08-17T14:16:30.027 に答える