Ich habe Vorlesungsvideos von Robert Sedgwick über Algorithmen durchgelesen, und er erklärt, dass zufälliges Shuffling dafür sorgt, dass wir nicht das schnellste quadratische Zeitszenario im Worst-Case-Fall finden. Aber ich kann nicht verstehen, wie.
Es ist wirklich ein Eingeständnis, dass obwohl wir oft von durchschnittlicher Fallkomplexität sprechen, erwarten wir in der Praxis nicht, dass jeder Fall mit derselben Wahrscheinlichkeit auftaucht.
Das Sortieren eines bereits sortierten Arrays ist in Quicksort der schlimmste Fall, da Sie jedes Mal, wenn Sie einen Pivot auswählen, feststellen, dass alle Elemente auf der gleichen Seite des Pivot platziert sind, sodass Sie sich nicht in zwei ungefähr gleiche Hälften teilen . Und oft wird dieser bereits sortierte Fall in der Praxis häufiger vorkommen als in anderen Fällen.
Wenn Sie die Daten nach dem Zufallsprinzip zuerst mischen, ist das ein schneller Weg, um sicherzustellen, dass alle Fälle mit der gleichen Wahrscheinlichkeit auftauchen. Daher ist dieser schlimmste Fall so selten wie jeder andere Fall.
Es ist erwähnenswert, dass es andere Strategien gibt, die gut mit bereits sortierten Daten umgehen, wie z. B. das mittlere Element als Drehpunkt auswählen.
Die Annahme ist, dass der schlimmste Fall - alles bereits sortiert - häufig genug ist, worüber man sich Sorgen machen sollte, und ein Shuffle ist eine schlimme Art und Weise, diesen Fall zu vermeiden, ohne das durch Verbesserung zugeben zu müssen In diesem Fall verschiebst du das Problem auf ein anderes, das zufälligerweise in eine sortierte Reihenfolge gemischt wird. Hoffentlich ist dieser schlimme Fall eine viel seltenere Situation, und selbst wenn es dazu kommt, bedeutet die Zufälligkeit, dass das Problem nicht einfach reproduziert werden kann und wird auf diesen Cheat zurückgeführt.
Das Konzept, einen gemeinsamen Fall auf Kosten eines seltenen zu verbessern, ist in Ordnung. Die Zufälligkeit als Alternative dazu, darüber nachzudenken, welche Fälle mehr oder weniger häufig vorkommen, ist etwas schlampig.
Im Fall von randomisiertem QuickSort können wir, da das Pivot-Element zufällig ausgewählt wird, erwarten, dass die Aufteilung des Input-Arrays im Durchschnitt durchschnittlich ist - im Gegensatz zu dem Fall von 1 und ( n-1) Split in einer nicht-randomisierten Version des Algorithmus. Dies hilft dabei, das Worst-Case-Verhalten von QuickSort zu verhindern, das bei unsymmetrischer Partitionierung auftritt.
Daher ist die durchschnittliche Laufzeit der randomisierten Version von QuickSort O (nlogn) und nicht O (n ^ 2);
Was bewirkt eine zufällige Mischung mit der Verteilung im Eingabebereich? Um das zu verstehen, betrachten wir eine Wahrscheinlichkeitsverteilung, P , die über eine Menge S definiert ist, wobei P nicht in unserer Kontrolle liegt. Lassen Sie uns eine Wahrscheinlichkeitsverteilung P' erstellen, indem Sie ein zufälliges Shuffle anwenden, über S bis P . Mit anderen Worten, jedes Mal, wenn wir ein Sample von P erhalten, ordnen wir es gleichmäßig zufällig einem Element von S zu. Was können Sie zu dieser resultierenden Verteilung P' sagen?
Somit ist P' nur die gleichmäßige Verteilung über S . Ein zufälliger Shuffle gibt uns die Kontrolle über die Eingabewahrscheinlichkeitsverteilung.
Wie ist das relevant für Quicksort? Nun, wir kennen die durchschnittliche Komplexität von Quicksort. Dies wird mit der einheitlichen Wahrscheinlichkeitsverteilung berechnet und das ist eine Eigenschaft, die wir in unserer Eingabeverteilung beibehalten wollen, unabhängig davon, was sie wirklich ist. Um dies zu erreichen, mischen wir unser Input-Array zufällig und stellen sicher, dass die Verteilung in keiner Weise kontradiktorisch ist.
Ist das Video in coursera ? Leider shuffle verringert die Leistung auf O (N ^ 2) mit den Daten n, n, ..., n, 1,1, ..., 1. Ich habe Quick.java mit nn11.awk , die solche Daten generieren.
%Vor%