Die zeitliche Komplexität des QuickSort -Algorithmus lautet wie folgt:
* Bester Fall: O (n log n)
* Durchschnittlicher Fall: O (n log n)
* schlimmster Fall: O (n^2)
Wo 'n' die Anzahl der Elemente im Array ist, wird sortiert.
Erläuterung:
* Bester und durchschnittlicher Fall (o (n log n)):
Dies tritt auf, wenn das Pivot -Element das Array konsistent in ungefähr gleiche Hälften unterteilt. Die Rekursionstiefe wird logarithmisch (log n), und auf jeder Rekursion führen wir eine lineare Menge an Arbeit (n), um das Array aufzuteilern. Daher ist die Gesamtkomplexität O (n log n).
* schlimmster Fall (o (n^2)):
Dies geschieht, wenn das Pivot -Element durchweg das kleinste oder größte Element der Subtarray ist. In diesem Szenario ist ein Subtarray leer und der andere enthält (N-1) Elemente. Dies führt zu einer sehr unausgeglichenen Rekursion, die den Algorithmus zu einer Selektionsart effektiv beeinträchtigt. Die Rekursionstiefe wird zu „n“, und auf jeder Ebene führen wir immer noch lineare Arbeiten aus, was zur Komplexität von O (n * n) =o (n^2) führt. Ein häufiges Szenario dafür ist, wenn das Eingangsarray bereits sortiert oder nahezu sortiert ist und das erste oder letzte Element als Drehpunkt ausgewählt wird.
Raumkomplexität:
Die Raumkomplexität von Quicksort hängt davon ab, ob Sie über die In-Place-Version sprechen oder nicht, und sie hängt auch von der Rekursionstiefe ab.
* Einstellungsquicksort (mit iterativer Implementierung zur Begrenzung der Rekursionstiefe): O (log n) im Durchschnitt aufgrund des Rekursionsstapels. Im schlimmsten Fall (obwohl durch die Schwanzanrufoptimierung oder ein explizites Stack -Management vermeitelt werden kann) kann es O (n) sein. Eine iterative Implementierung von QuickSort verwendet explizite Stapel, um Rekursionsaufrufe zu vermeiden. Daher ist die Raumkomplexität O (1).
* Non-in-Place-Quicksort: O (n) zusätzlichen Platz, um die Subtarrays während der Partitionierung zu speichern.
wichtige Überlegungen:
* Pivot -Auswahl: Die Auswahl des Drehzahl wirkt sich erheblich auf die Leistung von Quicksort aus. Strategien wie die Auswahl eines zufälligen Pivots, das Median der drei (ersten, mittleren, letztem) oder anspruchsvolleren Methoden können dazu beitragen, das Worst-Case-Szenario zu vermeiden und durchschnittlich die Leistung von O (n log n) zu erreichen.
* Einsieger gegenüber nicht in Ort: In-Place Quicksort modifiziert das Original-Array direkt und verringert die Notwendigkeit eines zusätzlichen Speichers. Nicht-Place-Versionen können die Partitionierungslogik vereinfachen, erfordern jedoch zusätzlichen Platz.
* Praktische Leistung: Quicksort wird oft als einer der schnellsten Sortieralgorithmen in der Praxis (insbesondere in den Implementierungen) angesehen, wenn es in vielen Fällen gut implementiert wird, und übertreffen Algorithmen wie Merge-Sortierung. Dies liegt an seinem relativ geringen Overhead und einer guten Cache -Auslastung. Es ist jedoch wichtig, sich des Potenzials für das Worst-Case-Szenario bewusst zu sein und geeignete Pivot-Auswahltechniken zu verwenden.
Zusammenfassend:Während Quicksort eine schlimmste Zeitkomplexität von O (n^2) hat, ist es im Allgemeinen ein sehr effizienter Sortieralgorithmus mit einer durchschnittlichen Zeitkomplexität von O (N log n). Der Schlüssel ist, einen guten Drehpunkt zu wählen, um das Worst-Case-Szenario zu vermeiden.
