Die Zeitkomplexität von Quicksort, die in der Big O -Notation ausgedrückt wird, hängt von den Eingabedaten ab:
* Bester Fall: O (n log n)
* Durchschnittlicher Fall: O (n log n)
* schlimmster Fall: O (n^2)
Hier ist eine Aufschlüsselung:
* Bester Fall und Durchschnittsfall (o (n log n)): Dies tritt auf, wenn das bei jedem Schritt ausgewählte Pivot -Element das Array in ungefähr gleiche Hälften unterteilt. In diesem Szenario führt der Algorithmus log und rekursive Anrufe (da er die Problemgröße effektiv halbiert) und für jede Rekursion erfordert O (n) Arbeit, um das Array zu partitionieren. Daher ist die Gesamtzeitkomplexität O (n log n).
* schlimmster Fall (o (n^2)): Dies geschieht, wenn das Pivot -Element wiederholt das kleinste oder größte Element im Array ist. Dies führt zu sehr ungleichmäßigen Partitionen. Anstatt das Array in zwei Hälften zu teilen, reduzieren Sie im Wesentlichen nur die Problemgröße jedes Mal um ein Element. Dies führt zu n rekursiven Aufrufen, und jeder Anruf braucht noch O (N) Zeit zur Partition (weil Sie fast alle Elemente vergleichen). Folglich nimmt die Gesamtzeitkomplexität auf O (n^2) ab.
Minderung des Worst-Case-Szenarios:
Das Worst-Case-Szenario kann gemindert werden durch:
* Randomisierte Pivot -Auswahl: Durch die zufällige Auswahl des Drehschalters zu vermeiden, dass das kleinste oder größte Element konsequent ausgewählt wird, wodurch der Fall O (n^2) viel weniger wahrscheinlich ist.
* Median-Drei-Pivot-Auswahl: Die Auswahl des Medians der ersten, mittleren und letzten Elemente des Arrays als Drehzahl kann auch dazu beitragen, eine konsequent schlechte Drehauswahl zu vermeiden.
In der Praxis ist QuickSort aufgrund seiner guten Durchschnittsfallleistung und der Tatsache, dass es tendenziell niedrigere konstante Faktoren hat als andere O-Sortieralgorithmen wie Merge-Sortier, häufig sehr effizient als andere O-Sortieralgorithmen. Es ist jedoch wichtig, sich des Potenzials für das Verhalten von O (n^2) bewusst zu sein.
