Der Versuch, die 2N lnN zu verstehen, führt zu einer Quicksortierung

Ich habe die Analyse von Quicksort in Sedgewicks Algorithmenbuch durchgearbeitet. Er erstellt die folgende Wiederholungsrelation für die Anzahl der Vergleiche in Quicksort, während er ein Array von N verschiedenen Elementen sortiert.

Es fällt mir schwer, das zu verstehen ... Ich weiß, dass jedes Element mit einer Wahrscheinlichkeit von 1 / N zum Pivot wird. Wenn k zum Pivot wird, hat das linke Sub-Array k-1 Elemente und das rechte Sub-Array k-1 Elemente. Array wird Nk Elemente haben.

1.Wie werden die Kosten für die Partitionierung zu N + 1? Benötigt man N + 1 Vergleiche, um die Partitionierung durchzuführen?

2.Sedgewick gibt für jeden Wert von k, wenn Sie diese addieren, die Wahrscheinlichkeit an, dass das Partitionierungselement k + die Kosten für die beiden Sub-Arrays ist. Sie erhalten die obige Gleichung.

• Kann jemand dies erklären, damit diejenigen mit weniger Mathematikkenntnissen (ich) verstehen können?
• Speziell wie bekommt man den zweiten Term in der Gleichung?
• Wofür genau steht dieser Begriff?

Die Kostenfunktion Cfür Quicksort besteht aus zwei Teilen. Der erste Teil sind die Kosten für die Aufteilung des Arrays in zwei "Hälften" (die Hälften müssen nicht gleich groß sein, daher die Anführungszeichen). Der zweite Teil sind die Kosten für das Sortieren dieser beiden Hälften.

1. Der (N + 1)Begriff ist eigentlich ein verkürzter Begriff und stammt aus den Begriffen

   (N - 1) + 2
   

   Dies sind die Kosten für die Partitionierung in Quicksort: N-1Vergleich mit dem Pivot-Wert und 2 zusätzliche Vergleiche aufgrund einiger Randbedingungen in der Partitionierung.

2. Der zweite Teil der Gleichung besteht aus den Kosten für das Sortieren der beiden Hälften auf beiden Seiten des Pivot-Werts k.

   Nachdem Sie einen Pivot-Wert ausgewählt haben, verbleiben zwei unsortierte 'Hälften'. Die Kosten für das Sortieren dieser "Hälften" hängen von ihrer Größe ab und werden am einfachsten als rekursive Anwendung der Kostenfunktion beschrieben C. Wenn der Drehpunkt der kleinste der NWerte ist, betragen die Kosten für das Sortieren der beiden Hälften jeweils C(0)und C(N-1)(die Kosten für das Sortieren eines Arrays mit 0 Elementen und die Kosten für das Sortieren eines Arrays mit N-1Elementen). Wenn der Drehpunkt der fünftkleinste ist, betragen die Kosten für das Sortieren der beiden Hälften jeweils C(5)und C(N-6)(die Kosten für das Sortieren eines Arrays mit 5 Elementen und die Kosten für das Sortieren eines Arrays mit N-6Elementen). Ähnliches gilt für alle anderen Pivot-Werte.

   Aber wie viel kostet es, diese beiden "Hälften" zu sortieren, wenn Sie den Pivot-Wert nicht kennen? Dies geschieht, indem die Kosten für jeden möglichen Wert des Pivots genommen und mit der Wahrscheinlichkeit multipliziert werden, dass dieser bestimmte Wert auftaucht.

   Da jeder Pivot-Wert gleich wahrscheinlich ist, können Sie einen bestimmten Pivot-Wert auswählen, 1/Nwenn Sie über NElemente verfügen . Um dies zu verstehen, überlegen Sie, ob Sie einen Würfel würfeln sollen. Bei einem richtigen Würfel ist die Chance, dass jede Seite nach oben zeigt, gleich, sodass die Chance, eine 1 zu würfeln, 1/6 beträgt.

   Zusammen ergibt dies den Summationsterm, bei dem für jeden möglichen Wert k des Pivots die Kosten ( C(k-1) + C(N-k)) mit der Chance ( 1/N) multipliziert werden.

3. Die weitere Herleitung der Summierungsformel in der Frage nach dem 2N lnNTitel erfordert zu viel Mathematik, um sie hier näher zu erläutern, basiert jedoch auf dem Verständnis, dass die Kosten für das Sortieren eines Arrays von NElementen ( C(N)) als Sortieraufwand ausgedrückt werden können Array von N-1Elementen ( C(N-1)) und einem Faktor, der direkt proportional zu ist N.

1. Es scheint, dass N + 1 als Anzahl der Vergleiche für den Partitionsschritt ein Fehler im Buch ist. Sie müssen für jedes der N – 1 Nicht-Pivot-Elemente herausfinden, ob es kleiner oder größer als der Pivot ist, für den ein Vergleich durchgeführt wird. also insgesamt N – 1 Vergleiche, nicht N + 1. (Betrachten Sie den einfachsten Fall, N = 2, dh ein Drehpunkt und ein anderes Element: Es gibt absolut keinen Raum für drei Vergleiche zwischen zwei Elementen.)

2. Betrachten Sie den Fall, in dem der gewählte Drehpunkt das kleinste Element ist (k = 1). Dies bedeutet, dass das Array in einen leeren Teil links (es gibt keine Elemente, die kleiner als der Drehpunkt sind) und einen Teil rechts unterteilt ist, der alle Elemente außer dem Drehpunkt enthält (alle anderen Elemente sind größer als der Drehpunkt) ). Dies bedeutet, dass die Teilprobleme, die Sie jetzt rekursiv lösen möchten, die Größen 0 und N – 1 (k – 1 bzw. N – k) haben und Vergleiche mit C (0) und C (N – 1) erfordern. somit ist C (0) + C (N – 1) insgesamt.

   Wenn der Pivot zufällig das zweitkleinste Element ist (k = 2), sind die Unterproblemgrößen 1 und N – 2 (k – 1 und N – k; ein Element links, da es das einzige ist, das kleiner als ist der Drehzapfen). Die rekursive Lösung dieser Unterprobleme erfordert daher C (1) + C (N – 2) -Vergleiche. Und so weiter, wenn der Drehpunkt das drittkleinste Element, das vierte usw. ist. Dies sind die Ausdrücke in den Zählern.

   Da der Drehpunkt zufällig aus den N Elementen ausgewählt wird, tritt jeder Fall (Drehpunkt ist am kleinsten, Drehpunkt ist am zweitkleinsten usw.) mit der gleichen Wahrscheinlichkeit 1 / N auf. Daher kommt das N im Nenner.