wake-up-neo.com

Intuitive Erklärung, warum QuickSort n log n ist?

Kann jemand ein "einfaches Englisch" intuitiv, aber formal erklären, was QuickSort n log n macht? Nach meinem Verständnis muss es einen Durchlauf über n Elemente machen, und es wird dieses Protokoll n-mal protokolliert.

40
Jim_CS

Für jede Partitionierungsoperation werden O(n) - Operationen ausgeführt (ein Durchlauf des Arrays) . Im Durchschnitt teilt jede Partitionierung das Array in zwei Teile auf (was logn-Operationen ergibt). Insgesamt haben wir O (n * log n) Operationen.

Das heißt in durchschnittlichen Log-n-Partitionierungsoperationen und jede Partitionierung erfordert O(n) -Operationen.

42
Eugene Retunsky

Der log n-Teil rührt von der Tatsache her, dass er (zumindest idealerweise) die Eingabe bei jeder Iteration halbiert. Wenn Sie mit N Elementen beginnen und diese jedes Mal in zwei Hälften zerlegen, bedeutet dies, dass Sie nach dem Protokollieren nur noch ein Element benötigen2(N) Iterationen, an diesem Punkt können Sie es offensichtlich nicht weiter unterteilen. Ausgehend von beispielsweise 128 Elementen unterteilen Sie sich in Gruppen von 64, 32, 16, 8, 4, 2, 1 Elementen - 7 Iterationen (und Protokoll)2(128) = 7).

Jede dieser Iterationen durchsucht das gesamte Array, um es zu partitionieren, sodass jede von ihnen O(N) - Komplexität aufweist.

Zwischen den beiden befinden sich O (log N) -Operationen, von denen jede O(n) -Komplexität hat, für O (n log n) Gesamtkomplexität.

Technisch korrekt ist das Big-O von Quicksort eigentlich O (N2) aber. Dies ergibt sich aus der Tatsache, dass eine ausreichend schlechte Wahl des Partitionselements das Array auf der einen Seite in ein Element und den gesamten Rest des Arrays auf der anderen Seite aufteilen könnte. Wenn dies bei jeder Iteration geschieht, sind N-Iterationen erforderlich, um es in Teile eines Elements zu zerlegen, so dass Sie insgesamt N Operationen mit jeweils einer Komplexität von O (N) für O (N * N) erhalten.

In einer realen Implementierung hören Sie normalerweise davor auf, aber das ist das am weitesten entfernte.

103
Jerry Coffin

Nun, es ist nicht immer n (log n). Es ist die Leistungszeit, wenn der ausgewählte Drehpunkt ungefähr in der Mitte liegt. Wenn Sie im schlimmsten Fall das kleinste oder das größte Element als Drehpunkt wählen, ist die Zeit 0 (n ^ 2).

Um 'n log n' zu visualisieren, können Sie davon ausgehen, dass das Pivot ein Element ist, das dem Durchschnitt aller zu sortierenden Elemente in dem Array am nächsten liegt. Dies würde das Array in 2 Teile von ungefähr derselben Länge unterteilen. In beiden Fällen wenden Sie das Quicksort-Verfahren an.

Da Sie in jedem Schritt die Länge des Arrays halbieren, tun Sie dies für log n (Basis 2), bis length = 1 erreicht wird, d. H. Ein sortiertes Array mit 1 Element.

2
Siddharth Gaur

Hinter den Logarithmen steckt eine wichtige Intuition:

Die Häufigkeit, mit der Sie eine Zahl n durch eine Konstante teilen können, bevor Sie 1 erreichen, ist O (log n).

Mit anderen Worten, wenn Sie eine Laufzeit mit einem O (log n) -Term sehen, besteht eine gute Chance, dass Sie etwas finden, das immer wieder um einen konstanten Faktor schrumpft.

In QuickSort schrumpft die Größe des größten rekursiven Aufrufs auf jeder Ebene um einen konstanten Faktor. Quicksort wählt einen Pivot aus, teilt das Array in zwei Unterfelder aus Elementen, die kleiner als der Pivot und größer als der Pivot sind, und sortiert dann jedes Unterfeld rekursiv.

Wenn Sie den Pivot nach dem Zufallsprinzip auswählen, liegt die Wahrscheinlichkeit, dass sich der ausgewählte Pivot in der Mitte von 50% der Elemente befindet, bei 50%. Dies bedeutet, dass die Wahrscheinlichkeit, dass das größere der beiden Subarrays höchstens 75% beträgt, bei 80% liegt Größe des Originals. (Verstehst du warum?)

Daher ist eine gute Intuition dafür, warum Quicksort in der Zeit O (n log n) ausgeführt wird, die folgende: Jede Ebene im Rekursionsbaum funktioniert O(n) und da jeder rekursive Aufruf ein hat Mit einer guten Chance, die Größe des Arrays um mindestens 25% zu verringern, würden wir erwarten, dass es O (log n) -Schichten gibt, bevor Sie keine Elemente mehr haben, die Sie aus dem Array entfernen können.

Dies setzt natürlich voraus, dass Sie Pivots nach dem Zufallsprinzip auswählen. Viele Implementierungen von Quicksort verwenden Heuristiken, um einen Nice-Pivot ohne zu viel Arbeit zu erhalten, und diese Implementierungen können im schlimmsten Fall leider zu schlechten Gesamtlaufzeiten führen. In der hervorragenden Antwort von @Jerry Coffin auf diese Frage geht es um einige Variationen von Quicksort, die das Verhalten von O (n log n) im schlimmsten Fall gewährleisten, indem Sie die verwendeten Sortieralgorithmen umschalten. Hier finden Sie weitere Informationen.

0
templatetypedef

Brechen Sie den Sortieralgorithmus in zwei Teile. Der erste ist der Partitionierungs- und der zweite rekursive Aufruf. Die Komplexität der Partitionierung ist O(N) und die Komplexität des rekursiven Aufrufs für den Idealfall ist O (logN). Wenn Sie beispielsweise 4 Eingaben haben, wird 2(log4) rekursiver Aufruf Multipliziert man beide, so erhält man O (NlogN). Dies ist eine sehr grundlegende Erklärung.

0
IT Worker

Tatsächlich müssen Sie die Position aller N-Elemente (Pivot) ermitteln, die maximale Anzahl der Vergleiche ist jedoch logN für jedes Element (der erste ist N, der zweite Pivot ist N/2,3. N/4.) das Medianelement)

0
Prdp