2N LNNを理解しようとすると、QuickSortの場合

Question

私はSedgewickのアルゴリズム本のQuickSortの分析を経験していました。彼は、N個の異なるアイテムの配列を並べ替えながら、クイックソートの比較数に対する次の再発関係を作成します。

これを理解する厳しい時間を過ごしています...私はそれがピボットになるために任意の要素に1 / nの確率がかかり、kがピボットになると、左サブアレイはK-1要素を持つことを知っています。右サブアレイにはNK要素があります。

1.仕切りコストはN + 1になりますか？ N + 1が分割を行うのに対応しますか？

2.Sedgewickは、kの各値について、それらを追加すると、分割要素がK +の確率が2つのサブアレイのコストである可能性があります。

• 誰かがこれを説明することができます。
• 特に式で2番目の用語を手に入れるのですか？
• その期間は正確に何が載っていますか？

Answer 1

QuickSort用のコスト関数Cは2つの部分で構成されています。最初の部分は、アレイを2つの半分に分割するためのコストです（半分は等しいサイズである必要はありません。したがって引用符を指定します）。 2つの部分は、それらの2つの半分をソートするためのコストです。

1. (N + 1)の用語は実際には凝縮期間であり、用語

   (N - 1) + 2
   

   .

   これはQuickSortのパーティション化のコストです.N-1はピボット値と比較し、パーティション化のある境界条件のために2つの追加の比較が比較されます。

2. 式の2番目の部分は、ピボット値kの両側に2つの「半分」をソートするためのコストで構成されています。

   ピボット値を選択した後、あなたは2つの非符号質「半分」を持ちます。これらの[半分]をソートするコストは、それらのサイズによって異なり、コスト関数Cの再帰的なアプリケーションとして最も簡単に説明されています。ピボットがN値の最小である場合、2つの「半分」のそれぞれをソートするためのコストはそれぞれC(0)とC(N-1)です（0要素を持つアレイを0個の要素を並べ替えるためのコストと、並び替えるためのコスト）。 ピボットが5番目に小さい場合、2つの「半分」のそれぞれをソートするためのコストはそれぞれN-1およびC(5)です（5つの要素を持つアレイをソートするためのコスト、および並び替えのためのコストとC(N-6)要素を並べ替えるためのコスト）。そして他のすべてのピボット値についても同様に。

   しかし、ピボット値がわからない場合は、これら2つの「半分」を並べ替えるのにいくらかかりますか？これは、ピボットのそれぞれの可能な値に対してコストを取得し、その特定の値が照らされた可能性を掛けて行われます。

   各ピボット値は等しくおそれがあるので、N-6要素がある場合は、特定のピボット値を選択する機会が1/Nです。これを理解するには、サイコロを転がすことについて考えてください。適切なサイコロでは、各側面が直面しているのが等しいので、1を転がす機会は1/6です。

   結合、これは、ピボットの可能な各値kに対して、コスト（N）にチャンス（C(k-1) + C(N-k)）

を掛けた合計項を与えます。

3. タイトル内の1/Nへの質問における総和式の派生は、ここで詳しく説明するために数の数学がかかりすぎるが、2N lnN要素の配列をソートするためのコストが理解に基づいている（N ）一般的なC(N)要素の配列（N-1）とC(N-1)に正比例する要因のソートに関して表現できます。

Answer 2

1. パーティションステップの比較数としてn + 1は本のエラーです。それが1つの比較をとるピボットよりも小さいかそれ以上のN - 1の非ピボット要素のそれぞれについて調べる必要がある。したがって、n - 1の比較は、n + 1ではなく、全体の比較。 （最も単純な場合は、n= 2、すなわち1つのピボットおよび他の要素を考える：2つの要素間の 3 比較を行う余地は全くありません。）

2. 選択したピボットが最小の要素（k= 1）である場合を考える。つまり、アレイが左側の空の部分に分割されていることを意味します（ピボットよりも小さい要素はありません）、ピボット以外のすべての要素を含む右側の部分は（他のすべての要素がピボットより大きい）。 ）。これは、現在、再帰的に再帰的にSizeD 0とN-1（K-1とN-K）を持ち、C（0）とC（N-1）の比較を必要とします。したがって、合計でC（0）+ C（N - 1）。

   ピボットが2番目に小さい要素（k= 2）である場合、副問題サイズは1とN - 2（K-1とN-kです。左側の1つの要素、唯一のものです。ピボットよりも小さいです）。したがって、これらの副問題を再帰的に解決することは、C（1）+ C（N - 2）の比較を必要とする。また、ピボットが3番目の最小要素、4番目の要素などの場合は、分子内の式です。

   ピボットは、N個の要素の中からランダムに選択されるため、それぞれの場合（ピボットは最小で、ピボットは2番目に小さいなど）が等しい可能性1 / nで発生します。それが分母のNが出身する場所です。