Wahrscheinlichkeit, dass zwei Elemente im randomisierten Quicksort verglichen werden

Question

Ich habe ein Problem in einem bestimmten Teil der randomisierten Schnellsortierungsanalyse.

Gemäß dem randomisierten Schnellsortierungsalgorithmus wird der Pivot aus der gegebenen Teilmenge, für die er aufgerufen wird, aus einem zufälligen Index ausgewählt, anstatt jedes Mal nur einen bestimmten Index auszuwählen.

Nehmen wir nun an, wir geben beispielsweise ein Array mit einer Größe an $n$ zu unserem randomisierten Quicksort-Algorithmus.

Nun möchte ich einen Blick auf den Beweis von Lemma-7.1 im unten angegebenen Text werfen.Jetzt haben wir unserem Algorithmus ein Array gegeben, das aus einer beliebigen Permutation der Elemente bestehen kann, jedoch in der Absatz direkt nach dem Beweis von $lemma-7.1$.

Warum berücksichtigt der Autor bei der Analyse eine sortierte Instanz unseres Eingabearrays?

Schauen Sie sich außerdem den Text nach der Gleichung an $(7.2)$ wo es ihre Logik gerechtfertigt hat, die Wahrscheinlichkeit dafür zu finden $z_i$ verglichen werden soll $z_j$ in unserem Algorithmus.Jetzt betrachten sie die Teilmenge {$z_i$,...,$z_j$}.Handelt es sich hierbei nicht um einen Vergleich von $z_i$,$z_j$ Werden wir zu spezifisch, wenn wir nur diese bestimmte Teilmenge betrachten?Ich möchte damit sagen, dass wir einen randomisierten Ansatz verwenden und die Vergleichswahrscheinlichkeit anhand einer breiteren Betrachtungsweise abgeleitet werden könnte, beispielsweise durch eine Permutation aller möglichen Fälle oder so.

Dass wir eine bestimmte Teilmenge verwenden und diese zu sortiert ist, ist nicht überzeugend, wie wir die richtige Wahrscheinlichkeit für unseren Algorithmus erhalten ...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |                           
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

Und die Wahrscheinlichkeit von $1/(j-i+1)$ -> Gesamtanzahlvon Elementen in der Untergruppe ist auch für spezifische festgelegt $i$ Und $j$

Bei der Betrachtung der Vergleichswahrscheinlichkeit von $z_i$,$z_j$, die Teilmenge, in der sich die beiden Elemente befinden und die aufgeteilt werden soll, kann beliebig (also aus jedem möglichen Element zusammengesetzt) ​​und beliebig groß (nicht nur) sein $j-i+1$)...

Vielleicht nimmt die Randomisierungsbedingung alles in Rechnung, aber ich bekomme sie nicht.Können Sie mir bitte die Logik erläutern, die sie verwenden, um die besagte Wahrscheinlichkeit zu ermitteln, und mich bitte auch davon überzeugen, dass wir die Vergleichswahrscheinlichkeit richtig ermitteln?

Als Referenz füge ich die entsprechenden Seiten von INTRODUCTION TO ALGORITHMS 3RD ED-- CLRS bei

Answer 1

Ein ganz einfacher Beweis:Ich behaupte, dass, wenn es d ganze Zahlen mit Werten zwischen x und y gibt und es n ≥ 2 Elemente im Array gibt, die Wahrscheinlichkeit, dass x und y verglichen werden, unabhängig von n 2 / (d + 2) beträgt.

Beweis durch Induktion:Wenn n = 2, dann ist eindeutig d = 0, daher wird behauptet, dass x und y mit der Wahrscheinlichkeit 2 / (0 + 2) = 1 verglichen werden.Dies ist auch eindeutig richtig, da x und y verglichen werden müssen.

Sei nun n ≥ 3.Für die erste Partitionierung wählen wir zufällig einen Pivot.Jedes Array-Element wird mit dem Pivot verglichen und es werden keine weiteren Vergleiche durchgeführt.Wenn wir also zufällig x oder y als Drehpunkt wählen, werden x und y verglichen.Die Wahrscheinlichkeit dafür beträgt 2 / n.Wenn wir zufällig eines der d Elemente mit Werten zwischen x und y auswählen, verschiebt die Partitionierung x in eine Partition und y in die andere, sodass sie nie verglichen werden.Wenn wir eines der anderen n - d - 2 Elemente auswählen, landen x und y in derselben Partition und werden durch Induktion mit der Wahrscheinlichkeit 2 / (d + 2) verglichen.

Die Wahrscheinlichkeit, dass x und y verglichen werden, beträgt also

2 / n + (n - d - 2) / n * 2 / (d + 2) = 

2 * (d + 2) / (n * (d + 2)) + 2 * (n - d - 2) / (n * (d + 2)) =

(d + 2 + n - d - 2) * 2 / (n * (d + 2)) =

2 * n / (n * (d + 2)) = 

2 / (d + 2) qed.

Das ist natürlich das gleiche Ergebnis wie Yuval, da | j - i | = D + 1.Die Randomisierung macht die Analyse ziemlich einfach – wenn wir zum Beispiel sagen würden: „Wenn n > 5, dann wählen wir 5 Elemente zufällig aus und wählen den Median dieser 5 als Pivot“, wäre die Analyse viel komplexer.

PS.Der Beweis in der Arbeit ist viel einfacher:Wenn Sie das Array partitionieren, $x_i$ Und $x_j$ Bleiben Sie in derselben Unterpartition, bis ein Pivot mit i <= Pivot <= j verwendet wird.Wenn dieser Drehpunkt i oder j ist, dann $x_i$ Und $x_j$ werden verglichen, andernfalls werden sie nicht verglichen.Die Chance beträgt also 2 / (abs (j-i) + 1).

Answer 2

Die Idee des Beweises besteht darin, für zwei beliebige Elemente zu berechnen $x,y$ im Array die Wahrscheinlichkeit, dass sie im Algorithmus verglichen werden.Diese Wahrscheinlichkeit könnte möglicherweise vom gesamten Array abhängen.Es stellt sich jedoch heraus, dass Sie es nur anhand der Bestellstatistiken von berechnen können $x,y$, das heißt ihre relative Reihenfolge im sortierten Array.Wenn du das weißt $x$ ist der $i$kleinstes Element im Array und das $y$ ist der $j$kleinstes Element im Array, dann ist die Wahrscheinlichkeit, dass $x,y$ verglichen werden $\frac{2}{|j-i|+1}$.

Dies ist kein Sonderfall – jedes Element $x$ im Array ist das $i$kleinstes Element, für einen Wert von $i$.Dies sind nur die relevanten Informationen, die es uns ermöglichen, die Wahrscheinlichkeit dafür zu berechnen $x$ Und $y$ werden verglichen.