algorithm - Selectアルゴリズムの良いピボットと「悪いピボット」の違いは何ですか?

Question

Select アルゴリズムを理解しようとしていますが、a good pivot VS a bad pivot. Partitionアルゴリズムは、ピボットの右側にある大きな要素とピボットの左側にある小さな要素を分離するためにアルゴリズムを使用していることがわかります。

• しかし、それはどういう意味bad pivotですか？
• 総実行時間をどのようにbad pivot投入できO(n^2)ますか?

ありがとう

Answer 1

各ステップで配列の巨大なチャンクを破棄できる場合、選択アルゴリズムは高速になります。適切なピボットとは、「ロット」の定義によって、アルゴリズムが配列要素の「ロット」を破棄することです。悪いピボットとは、アルゴリズムが配列のタイトルそのものを破棄するピボットです。

最悪の場合、ピボットは配列の最大または最小の要素である可能性があります。これが発生した場合、ピボットよりも小さい要素がないか、ピボットよりも大きい要素がないため、アルゴリズムは値の1つのグループが空になるように要素を分割します。この分割ステップには時間O（n）がかかり、反復ごとに配列のサイズが1つ減少するため、O（n）回実行する必要があります。これにより、アルゴリズムの実行時間がO（n ²）に低下します。興味深いことに、これは時間O（n ²）に縮退するクイックソートを取得する方法でもあります。

お役に立てれば！