Die zeitliche Komplexität von Quicksort, wenn das erste Element als Drehpunkt ausgewählt wird:
* Worst-Case:O (n^2)
* Best-Case:O (N log n)
* Durchschnittsfall:O (n log n)
Erläuterung:
* Worst-Case:O (n^2)
Dies tritt auf, wenn das Eingangsarray bereits sortiert ist (entweder in aufsteigender oder absteigender Reihenfolge) oder fast sortiert. Wenn das Array sortiert ist, ist der Drehpunkt immer das kleinste (oder größte) Element. Dies führt zu sehr unausgeglichenen Partitionen.
Zum Beispiel, wenn das Array in aufsteigender Reihenfolge sortiert ist und das erste Element immer der Drehpunkt ist:
1. Das erste Element wird als Drehpunkt ausgewählt.
2. Alle anderen Elemente sind größer als der Drehpunkt, so dass sie alle in der richtigen Trennwand enden.
3. Die linke Partition ist leer.
4. Der rekursive Anruf wird dann auf einem Teil der Größe `n-1` getätigt.
Dieser Vorgang wiederholt sich und führt zu einer Rekursionstiefe von "n". Auf jeder Ebene `Ich bin der Rekursion führen wir" n - ich "vergleiche. Die Gesamtzahl der Vergleiche wird ungefähr `n + (n-1) + (n-2) + ... + 1`, was gleich` n (n + 1)/2` ist, das ist o (n^2).
* Best-Case:O (N log n)
Das Best-Case-Szenario tritt auf, wenn der Drehpunkt das Array konsequent in zwei gleiche (oder nahezu gleiche) Hälften unterteilt. In dieser Situation wird die Rekursionstiefe zu "log n", und auf jeder Ebene führen wir "n" -Ge -Vergleiche durch, was zu einer zeitlichen Komplexität von "O (n log n)" führt.
* Durchschnittsfall:O (n log n)
Im Durchschnitt spielt Quicksort sehr gut. Wenn die Pivot -Auswahl durchweg einverstanden ausgewogene Partitionen erzeugt, lautet die zeitliche Komplexität "O (n log n)`. Der "durchschnittliche" geht davon aus, dass die Eingabe zufällig geordnet wird und die Pivot -Auswahl nicht durchweg schlecht ist.
Einfluss der Pivot -Wahl:
Die Auswahl von Drehungen wirkt sich erheblich auf die Leistung von Quicksort aus. Die Auswahl des ersten Elements als Pivot ist eine naive Strategie und kann in vielen gemeinsamen Situationen zum Worst-Case-Szenario führen.
Minderungstechniken:
Um das Worst-Case-Szenario bei der Verwendung von Quicksort zu vermeiden, ist es wichtig, einen guten Drehpunkt zu wählen. Hier sind einige gängige Techniken:
* Zufälliger Drehpunkt: Die Auswahl eines zufälligen Elements als Pivot ist ein einfacher und effektiver Weg, um das Worst-Case-Szenario zu vermeiden. Dies macht die Leistung des Algorithmus weniger von der anfänglichen Reihenfolge der Eingabe abhängig.
* Median-of-Drei: Wählen Sie den Median der ersten, mittleren und letzten Elemente des Arrays als Drehzahl. Dies bietet oft einen besseren Drehpunkt als einfach das erste Element auszuwählen.
* Andere Pivot -Auswahlstrategien: Es gibt anspruchsvollere Strategien für die Auswahl von Pivots, aber sie fügen häufig einen Overhead hinzu, der ihre Vorteile für typische Anwendungsfälle überwiegt.
Zusammenfassend:
Die Verwendung des ersten Elements als Drehpunkt in Quicksort kann eine schlechte Strategie sein, insbesondere wenn das Input -Array wahrscheinlich sortiert oder nahezu sortiert wird. Es ist am besten, Pivot-Auswahlstrategien zu verwenden, die versuchen, ausgewogenere Partitionen zu erstellen, um sicherzustellen, dass der Algorithmus näher an der Zeitkomplexität des Durchschnittsfalls `O (n log n) arbeitet.
