Ich lese " Probability and Computing " von M.Mitzenmacher und E.Upfal. Ich habe Probleme zu verstehen, wie die Wahrscheinlichkeit des Vergleichs zweier Elemente berechnet wird.
Eingabe: sortierte Liste (y1, y2, ..., yN) von Zahlen. Wir suchen nach einem Pivot-Element (zufällig). Frage: Was ist die Wahrscheinlichkeit, dass zwei Elemente yi und yj (j & gt; i) verglichen werden?
Antwort (aus Buch): yi und yj werden verglichen, wenn entweder yi oder yj als Pivot in der ersten Auslosung aus der Sequenz ausgewählt wird (yi, yi + 1, ..., yj- 1, yj). Also ist die Wahrscheinlichkeit: 2 / (j-i + 1).
Das Problem ist für mich die anfängliche Behauptung: Wenn man zum Beispiel yi in der ersten Auslosung von der ganzen Liste aufnimmt, wird der Vergleich mit yj (und umgekehrt) und die Wahrscheinlichkeit ist 2 / n.
Es ist also eher die "reverse" Behauptung wahr - keines der (yi + 1, ..., yj-1) Elemente kann vor yi oder yj ausgewählt werden, aber die "Pool" Größe ist nicht festgelegt ( in der ersten Ziehung ist es N sicher, aber auf der zweiten ist es kleiner).
Könnte jemand bitte erklären, wie die Autoren zu solch einer vereinfachten Schlussfolgerung kommen?
Edit1: einige gute Seele poliert meinen Beitrag, danke: -).
Edit2: Die Liste wird anfänglich sortiert.
Die Antwort der Autoren ist richtig, obwohl ich immer noch nicht sehe, wie sie leicht und schnell zu dem Schluss gekommen sind.
Bezeichne mit L = j-i + 1. Die tatsächlichen Werte von j und i spielen hier keine Rolle, was zählt, ist L. Bezeichnen wir auch die Wahrscheinlichkeit von P (N, L), yi und yj aus der geordneten Folge von Zahlen der Größe N zu vergleichen.
Fakten:
Diese Summe sieht hässlich aus, aber nach zwei Tests schien es, dass P (N, L) wahrscheinlich gleich 2 / L ist. Lass es uns überprüfen:
Und da L = j-i + 1 ist, erhalten wir 2 / (j-i + 1).
Quicksort vergleicht jedes Element mit dem Drehpunkt: diejenigen, die größer als der Drehpunkt sind, werden rechts vom Drehpunkt platziert, und diejenigen, die links nicht größer sind (oder umgekehrt, wenn Sie eine absteigende Sortierung wünschen, tut es nicht. t Angelegenheit).
Bei jedem Schritt wird der Drehpunkt aus einer Sequenz (yi, yi+1, ..., yj) ausgewählt. Wie viele Elemente in dieser Sequenz? j - i + 1 (Ich glaube, Sie hatten einen Tippfehler, es kann nicht y - i + 1 sein).
Also ist die Wahrscheinlichkeit, eines von zwei spezifischen Elementen aus dieser Liste auszuwählen, offensichtlich 2 / (j - i + 1) .
Das Problem für mich ist der anfängliche Anspruch: Wenn Sie zum Beispiel yi in der ersten Auslosung von der ganzen Liste aufnehmen, wird der Vergleich mit yj (und umgekehrt) und die Wahrscheinlichkeit ist 2 / n.
Das Auswählen von yi bewirkt, dass es nur mit den anderen j - i -Elementen verglichen wird. Woher hast du n ? Denken Sie daran, dass Ihre Liste nur von yi nach yj geht!
Bearbeiten :
Wenn ich die Frage noch einmal lese, finde ich es ein wenig mehrdeutig. Die Wahrscheinlichkeit, zwei Elemente im ersten Schritt der Rekursion zu vergleichen ist tatsächlich 2 / n , wie Sie sagen, weil i und j 1 und n sind. Die Wahrscheinlichkeit, zwei Elemente bei einem unbekannten rekursiven Schritt zu vergleichen , ist das, was ich oben erklärt habe.
Tags und Links algorithm probability quicksort