誰かがQuicksortとRandomized Quicksortの違いを明確にすることはできますか？

Question

ランダムなピボットを選択した場合と、順序のないセット/リストの最初のピボットを選択した場合の違いは何ですか？

セットは、それ自体がランダムなセット、の最初の値を選択イマイチ、順不同ですか？だから本質的に、私はランダム化がより良い最悪の場合のランタイムを約束するかどうかを理解しようとしています。

Answer 1

のコンセプトを任意のとのランダムと混在させている可能性があります。それはの任意ので、配列の最初の要素を選択することができます。あなたは好きな要素を選ぶことができますが、同様にうまくいくでしょうが、ではなくです。 ランダムは、あらかじめ予測することができないものです。 任意ののいずれかを選択できます。

並べ替えられたシーケンス1,2,3,4,5,6、...、nでクイックソートを使用しているとしましょう。最初の要素をピボットとして選択すると、ピボットとして1が選択されます。すべてのn - 1個の他の要素は右に行き、何も左にはなく、あなたは再帰的に2、3、4、5、...、nのクイックソートを行います。

この範囲をクイックソートすると、2がピボットとして選択されます。要素を分割すると、左には何も置かれず、右に3,4,5,6、...、nという数字が表示されるので、3、4、5、6、...、nのように再帰的にクイックソートされます。

より一般的には、kステップの後に、番号kをピボットとして選択し、右に数字k + 1、k + 2、...、nを入れ、再帰的にクイックソートします。あなたは、n-1の要素を見ている（、パーティション2に、3 ...、nは約1）最初のパスであるため、ここで行わ

総仕事は、Θ（nは）なってしまいます、 （2、3、4、5、...、nを2にする）場合、n-2個の要素などを調べなければなりません。これは、（n-1）+（n- 2）+ ... +1 = Θ（n ）、非常に非効率的です！

ここでは、これをランダム化クイックソートと対照しています。ランダム化されたクイックソートでは、実際には、各ステップでランダム要素をピボットとして選択します。これは、技術的にがの場合、決定論的な場合と同じピボットを選択することはできませんが、これは起こりにくく、確率が非常に低いことになります（確率は約2 ^{2 - n}）動作。配列の中心に近いピボットを選択する可能性が高くなります。そのとき、再帰はより均等に分岐し、より高速に終了します。

ランダム化されたクイックソートの利点は、入力が常にΘ（n log n）で実行される入力がなく、ランタイムがO（n log n）であることが予想されることです。決定論的クイックソートアルゴリズムは、通常、（1）それらがしかし高い一定の係数と、（N Nログ）最悪の場合の時間Oで実行され、または（2）それらは（N 最悪の場合の時間Oで実行いずれかという欠点を有しています）、このケースを引き起こす入力の種類は確定的です。