algorithm - クイック選択でのピボット要素選択

Question

クイック選択のために最後の要素に対してランダムなピボットを選択する意味はありますか?

常に最後の要素をピボットとして選択することで、必要な要素を見つけることができます。ランタイムに影響しますか。

Answer 1

ピボットの選択は、特定の配列でのクイック選択の実行時間に大きな影響を与えます。

決定論的クイック選択では、常に最後の要素をピボットとして選択する場合、常にソートされたリストから選択しようとするとどうなるか想像してみてください。ピボットは常に可能な限り最悪のピボットであり、配列から 1 つの数値のみを削除するため、Θ(n ² ) ランタイムが発生します。

ランダム化されたクイック選択では、再帰呼び出しごとにアルゴリズムが常に最悪の選択を行う場合、ランタイムが Θ(n ² )になる可能性は依然として技術的にはありますが、これは非常にありそうもないことです。ランタイムは高い確率で O(n) になり、「キラー」入力はありません。

言い換えると、決定論的に選択されたピボットを使用したクイックセレクトには常に、時間 Θ(n ² ) で実行するように強制する少なくとも 1 つの「キラー」入力がありますが、ランダム ピボットを使用したクイック選択にはキラー入力がなく、優れた平均時間保証があります。 . その結果、分析はまったく異なります。

お役に立てれば！