Warum hat Randomized Quicksort O (n log n) Worst-Case-Laufzeitkosten?

Randomized Quick Sort ist eine Erweiterung von Quick Sort, bei der das Pivot-Element zufällig ausgewählt wird. Was kann der schlimmste Fall sein, Zeit Komplexität dieses Algorithmus. Meiner Meinung nach sollte es , da der schlimmste Fall ein zufällig gewählter Drehpunkt in sortierter oder umgekehrter sortierter Reihenfolge ist. In einigen Texten [1] [2] wird die Zeitkomplexität im schlimmsten Fall als$O(n^2)$O ( n log n )$O(n\log{n})$

Was ist richtig?

Beide Quellen beziehen sich auf die "Worst-Case-Expected-Runtime" von Ich vermute, dies bezieht sich auf den erwarteten Zeitaufwand, der sich vom absolut schlechtesten Fall unterscheidet.$O(n \log n).$

Quicksort hat normalerweise einen absoluten Worst-Case-Zeitbedarf von . Der schlimmste Fall tritt auf, wenn bei jedem Schritt, das Trennverfahren einer aufspaltet n -Länge Array in Arrays der Größe 1 und n - 1 . Diese "unglückliche" Auswahl von Pivot-Elementen erfordert O ( n ) rekursive Aufrufe, was zu einem O ( n 2 ) Worst-Case führt.$O(n^2)$$n$$1$$n-1$$O(n)$$O(n^2)$

Die zufällige Auswahl des Pivots oder das zufällige Mischen des Arrays vor dem Sortieren hat zur Folge, dass der ungünstigste Fall, insbesondere bei großen Arrays, sehr unwahrscheinlich wird. Siehe Wikipedia für einen Beweis, dass der erwartete Zeitbedarf . Laut einer anderen Quelle ist "die Wahrscheinlichkeit, dass Quicksort eine quadratische Anzahl von Vergleichen verwendet, wenn ein großes Array auf Ihrem Computer sortiert wird, viel geringer als die Wahrscheinlichkeit, dass Ihr Computer vom Blitz getroffen wird".$O(n\log n)$

Bearbeiten:

Gemäß Bangyes Kommentar können Sie die Pivot-Auswahlsequenz für den ungünstigsten Fall eliminieren, indem Sie immer das Medianelement als Pivot auswählen. Da das Finden des Medians Zeit benötigt, ergibt dies Θ ( n log n ) Worst-Case-Performance. Da es jedoch sehr unwahrscheinlich ist, dass eine randomisierte Quicksortierung auf den schlimmsten Fall stößt, wird die deterministische Medianfindungsvariante der Quicksortierung selten verwendet.$O(n)$$\Theta(n \log n)$

Sie fehlten , dass diese Texte über „schlimmste Fall sprechen erwartete Laufzeit“, nicht „worst case Laufzeit“.

Sie diskutieren eine Quicksort-Implementierung, die ein zufälliges Element enthält. Normalerweise haben Sie einen deterministischen Algorithmus, dh einen Algorithmus, der für eine bestimmte Eingabe immer genau die gleichen Schritte erzeugt. Um die "Worst-Case-Laufzeit" zu bestimmen, untersuchen Sie alle möglichen Eingaben und wählen diejenige aus, die die schlechteste Laufzeit erzeugt.

Aber hier haben wir einen Zufallsfaktor. Bei bestimmten Eingaben führt der Algorithmus nicht immer dieselben Schritte aus, da eine gewisse Zufälligkeit vorliegt. Anstatt eine Laufzeit für jede feste Eingabe zu haben, haben wir eine "erwartete Laufzeit" - wir prüfen jeden möglichen Wert der zufälligen Entscheidungen und ihre Wahrscheinlichkeit, und die "erwartete Laufzeit" ist der gewichtete Durchschnitt der Laufzeit für jede Kombination von zufälligen Entscheidungen , aber immer noch für einen festen Eingang.

Wir berechnen also die "erwartete Laufzeit" für jede mögliche Eingabe, und um die "erwartete Laufzeit im schlechtesten Fall" zu erhalten, finden wir die eine mögliche Eingabe, bei der die erwartete Laufzeit am schlechtesten ist. Und anscheinend haben sie gezeigt, dass der schlechteste Fall für die "erwartete Laufzeit" nur O (n log n) ist. Es würde mich nicht überraschen, wenn das zufällige Auswählen des ersten Pivots die erwartete Laufzeit im schlimmsten Fall auf o (n ^ 2) (kleines o anstelle von großes O) ändern würde, da nur wenige von n Pivots zum schlimmsten Fall führen Verhalten.

Beachten Sie, dass es zwei Dinge gibt, die Sie als Erwartung / Durchschnitt ansehen müssen: die Eingabepermutation und die Pivots (eine pro Partitionierung).

$n$$\Theta(n \log n)$

$\Theta(n \log n)$

Unterm Strich überprüfen Sie Ihre (n) Quelle (n), für welche Implementierung sie verwenden und welche Menge sie als zufällig bzw. zufällig betrachten. in ihrer Analyse behoben.

$O(n^2)$

Der schlimmste Fall für zufällige Quicksortierung sind dieselben Elemente wie für die Eingabe. Beispiel: 2,2,2,2,2,2

$T(n) = T(n-1) + n$$O(n^2)$