If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Analyse von Quicksort

Wie kommt es, dass sich die Worst-Case- und die Durchschnitts-Laufzeit von Quicksort unterscheiden? Beginnen wir mit der Betrachtung der Worst-Case Laufzeit. Angenommen, wir haben Pech und die Partitionsgrößen sind unausgeglichen. Angenommen, der Pivot, der durch die Funktion partition gewählt wird, ist immer entweder das kleinste oder das größte Element im n-Elemente-Subarray. Dann wird eine der Partitionen keine Elemente enthalten und die andere Partition enthält n1 Elemente - also alle Elemente außer dem Pivot. So werden die rekursiven Anrufe auf Subarrays der Größen 0 und n1 ausgeführt.
Wie in Mergesort, ist die benötigte Zeit für einen rekursiven Anruf auf ein Subarray mit n Elementen Θ(n). In Mergesort war das die benötigte Zeit zum Kombinieren, wohingegen es in Quicksort die Zeit für die Partitionierung ist.

Worst-Case Laufzeit

Wenn Quicksort immer mit den asymmetrischsten Partitionen arbeiten muß, dann nimmt der erste Aufruf cn Zeit in Anspruch, wobei c eine Konstante ist. Der rekursive Anruf auf n1 Elemente dauert c(n1) Zeit, der rekursive Anruf auf n2 -Elemente dauert c(n2), und so weiter. Hier ist ein Baumdiagramm der Unterproblem-Größen mit ihren jeweiligen Partitionierungszeiten:
Diagramm der Worst-Case-Leistung für Quick Sort, mit einem Baum auf der linken Seite und Partitionszeiten auf der rechten Seite. Die erste Ebene des Baums zeigt einen einzelnen Knoten n und eine entsprechende Partitionierungszeit von c mal n. Die zweite Ebene des Baums zeigt zwei Knoten, 0 und n minus 1, und eine Partitionierungszeit von c mal n minus 1. Die dritte Ebene des Baums zeigt zwei Knoten, 0 und n minus 2, und eine Partitionierungszeit von c mal n minus 2. Die vierte Ebene des Baums zeigt zwei Knoten, 0 und n minus 3, und eine Partitionierungszeit von c mal n minus 3. Unterhalb dieser Ebene zeigen Punkte an, dass der Baum so weitergeht. Die vorletzte Ebene im Baum hat einen einzelnen Knoten 2 mit einer Partitionierungszeit von 2 mal c und die letzte Ebene hat zwei Knoten 0 und 1, mit einer Partitionierungszeit von 0.
Wenn wir die Partitionierungszeiten für jede Ebene addieren, erhalten wir
cn+c(n1)+c(n2)++2c=c(n+(n1)+(n2)++2)=c((n+1)(n/2)1) .
Die letzte Zeile sieht etwas eigenartig aus. Wieder haben wir es mit einer arithmetischen Reihe zu tun, die wir bereits bei der Analyse von Selectionsort angetroffen haben. 1+2+3++n ist eine arithmetische Reihe von der wir 1 subtrahieren, weil bei Quicksort die Summation bei 2 und nicht bei 1 beginnt (Versuche es selbst: Angenommen, n ist 5, dann haben wir c(5+4+3+2)) Wir haben einige niederwertige Terme und konstante Koeffizienten, aber wenn wir Big-Θ Notation verwenden, ignorieren wir diese. In Big-Θ Notation ist Quicksorts Worst-Case Laufzeit Θ(n2).

Best-Case Laufzeit

Quicksorts Best-Case Fall liegt vor, wenn die Partitionen so ausgeglichen wie möglich sind: Ihre Größen sind entweder gleich oder liegen nur um 1 auseinander. Der erste Fall tritt auf, wenn das Subarray eine ungerade Anzahl von Elementen hat, das Pivot nach der Partitionierung in der Mitte ist, und jede Partition genau (n1)/2 Elemente hat. Der letztere Fall tritt auf, wenn das Subarray eine gerade Zahl n von Elementen hat und eine Partition n/2 Elemente und die andere Partition n/21 Elemente hat. In jedem dieser Fälle hat jede Partition höchstens n/2 -Elemente, und der Baum der Unterproblem-Größe ähnelt dem Baum der Unterproblem-Größe von Mergesort, wobei die Partitionierung-Zeiten von Quicksort wie die Kombinations-Zeiten von Mergesort aussehen:
Diagramm der Best-Case-Leistung für Quick Sort, mit einem Baum auf der linken Seite und Partitionierungszeiten auf der rechten Seite. Die erste Ebene des Baums zeigt einen einzelnen Knoten n und eine entsprechende Partitionierungszeit von c mal n. Die zweite Ebene des Baums zeigt zwei Knoten, von denen jeder kleiner oder gleich 1/2 n ist, und eine Partitionierungszeit von kleiner oder gleich 2 mal c mal 1/2 n, was gleich c mal n ist. Die dritte Ebene des Baumes zeigt vier Knoten, jeder kleiner oder gleich 1/4 n, und eine Partitionierungszeit kleiner oder gleich 4 mal c mal 1/4 n, gleich c mal n. Die vierte Ebene des Baumes zeigt acht Knoten, jeder kleiner oder gleich 1/8 n, und eine Partitionierungszeit kleiner oder gleich 8 mal c mal 1/8 n, gleich c mal n. Unterhalb dieser Ebene sind Punkte dargestellt, um anzuzeigen, dass der Baum so weitergeht. Es wird eine letzte Ebene mit n Knoten von 1 und einer Partitionierungszeit von kleiner oder gleich n mal c, gleich c mal n, angezeigt.
Mit der Big-Θ Notation erhalten wir das gleiche Ergebnis wie für Mergesort: Θ(nlog2n).

Durchschnittliche Laufzeit

Um zu zeigen, dass die durchschnittliche Falllaufzeit auch Θ(nlog2n) ist, ist mathematisch aufwändig, was den Rahmen dieses Artikels sprengen würde. Aber wir können gewisse Überlegungen anstellen, indem wir uns ein paar Fälle anschauen, um zu verstehen, warum es O(nlog2n) sein könnte. (Sobald wir O(nlog2n) bestimmt haben, folgt Θ(nlog2n), da die durchschnittliche Laufzeit nicht besser sein kann als die Best-Case Laufzeit.) Angenommen, dass wir nicht immer gleichmäßig balancierte Partitionen erhalten, aber dass wir im schlimmsten Fall eine 3-zu-1 Teilung bekommen. Das bedeutet, dass nach jeder Partitionierung eine Seite 3/4n Elemente enthält und die andere Seite 1/4n. (Zur Vereinfachung vernachlässigen wir das Pivot.) Dann würde der Baum der Unterproblem-Größen und der jeweiligen Partitionierungszeiten so aussehen:
Diagramm der durchschnittlichen Performance für Quicksort
Das linke Kind eines jeden Knotens repräsentiert ein Unterproblem der Größe 1/4, und das rechte Kind stellt ein Unterproblem der Größe 3/4 dar. Die kleineren Unterproblem sind also alle auf der linken Seite. Folgen wir dem Pfad der linken Kinder, erreichen wir von der Wurzel ausgehend ein Unterproblem der Größe 1 schneller als auf irgendeinem anderen Pfaden. Wie die Abbildung zeigt, erreichen wir nach log4n Ebenen, eine Unterproblem-Größe von 1 . Warum log4n Ebenen? Zur Erklärung arbeiten wir einfach rückwärts und beginnen mit einer Unterproblem-Größe von 1 und multiplizieren sie mit dem Kehrwert von 1/4, also 4, bis wir n erreichen. Anders ausgedrückt suchen wir den Wert von x für den 4x=n ist? Die Antwort lautet log4n. Folgen wir nun dem Pfad der rechten Kinder. Die Abbildung zeigt, dass es log4/3n Ebenen dauert, bis man zu einem Unterproblem der Größe 1 kommt. Warum log4/3n Ebenen? Da jedes rechte Kind 3/4 der Größe des Knotens über ihm ist (sein Eltern-Knoten), ist jedes Elternteil 4/3 der Größe seines rechten Kindes. Erneut beginnen mit einem Unterproblem der Größe 1 multiplizieren es mit 4/3, bis wir n erreichen. Für welchen Wert von x ist (4/3)x=n? Die Antwort lautet log4/3n.
In jeder der ersten log4n Ebenen gibt es n Elemente (einschließlich Pivots, die in Wirklichkeit nicht mehr partitioniert werden), und so ist die gesamte Partitionierungszeit für jede dieser Ebenen cn. Aber was ist mit dem Rest der Ebenen? Jeder hat weniger als n Knoten, und so ist die Partitionierungszeit für jede Ebene höchstend cn. Insgesamt gibt es log4/3n Ebenen, und so ist die gesamte Partitionierungszeit O(nlog4/3n). Nun kann man die Basis von Logarithmen wie folgt umrechnen:
logan=logbnlogba
Das gilt für alle positiven zahlen a, b und n. Setzen wir nun a=4/3 und b=2, erhalten wir
log4/3n=log2nlog2(4/3) ,
Und somit unterscheiden sich log4/3n und log2n nur durch einen konstanten Faktor log2(4/3). Da konstante Faktoren bei der Verwendung der Big-O-Notation keine Rolle spielen, können wir feststellen, dass wenn alle Partitionierungen im Verhältnis von 3-zu-1 erfolgen, die Laufzeit von Quicksort O(nlog2n) ist, obschon mit einem größeren verborgenen konstanten Faktor als die Best-Case-Laufzeit.
Wie oft sollten wir eine Partitionierung erwarten, die 3-zu-1 oder besser ist? Es hängt davon ab, wie wir das Pivot wählen. Angenommen, die Wahrscheinlichkeit ist gleichmäßig verteilt, dass das Pivot nach der Partitionierung irgendwo in einem n -Elemente-Subarray anzutreffen ist. Um eine Partitionierung zu erhalten, die 3-zu-1 oder besser ist, müsste das Pivot irgendwo in der "mittleren Hälfte" liegen:
Also, wenn das Pivot nach der Partitionierung mit gleicher Wahrscheinlichkeit irgendwo im Subarray anzutreffen ist, gibt es eine 50% Wahrscheinlichkeit für eine 3-zu-1-Partitionierung oder besser. Mit anderen Worten, wir erwarten eine Partitionierung von 3-zu-1 oder besser in etwa der Hälfte der Fälle.
Der andere Fall, den wir uns anschauen wollen, um zu verstehen, warum Quicksorts durchschnittliche Laufzeit O(nlog2n) ist, ist dieser: Was passiert in der Hälfte der Fälle, in denen wir keine 3-to-1 Partitionierung bekommen, und im Extremfall die Worst-Case Partitionierung erhalten (also unbalancierte Partitionen wie weiter oben beschrieben). Nehmen wir an, dass die 3-zu-1- und Worst-Case-Partitionierungen abwechseln. Wir betrachten einen Knoten im Baum mit k -Elementen und seine Subarrays. Dann erhalten wir einen Teilbaum, der so aussieht:
anstelle von:
Selbst wenn wir die Worst-Case Partitionierung in 50% der Fälle und ansonsten die 3-zu-1 oder besser Partitionierung erhalten, dann wäre die Laufzeit etwa doppelt so groß wie die Laufzeit unter Verwendung einer regelmäßigen 3-zu-1 Partitionierung . Auch das ist wieder nur ein konstanter Faktor, der in der Big-O-Notation vernachlässigt werden darf, und gilt auch in diesem Fall die Laufzeit-Größenordnung O(nlog2n).
Wir dürfen aber nicht vergessen, dass diese Analyse nicht mathematisch rigoros ist, aber sie vermittelt uns eine intuitive Vorstellung davon, warum die Größenordnung der durchschnittlichen Laufzeit O(nlog2n) sein könnte.

Zufällige Auswahl des Pivotelements

Angenommen, dein schlimmster Feind hat dir ein Array gegeben, dass du mit Quicksort sortieren sollst. Er weiß, dass du immer das rechte Element in jedem Subarray als Pivot wählst und hat deswegen das Array so arrangiert, dass du immer die Worst-Case-Partitionierung bekommst. Was kannst du dagegen tun?
Du musst ja nicht unbedingt das rechte Element in jedem Subarray als Pivot wählen. Stattdessen könntest du zufällig ein Element im Subarray auswählen und dieses Element als Pivot verwenden. Aber halt mal - die partition-Funktion geht davon aus, dass sich das Pivot in der rechten Position des Subarrays befindet. Kein Problem - vertausche einfach das Element, das du als das Pivot gewählt hast, mit dem rechten Element und partitioniere dann wie gewohnt. Wenn dein Feind nicht weiß, wie du zufällige Stellen im Subarray wählst, gewinnst du!
Mit ein wenig mehr Aufwand könnest du die Wahrscheinlichkeit erhöhen, eine Partitionierung zu erhalten, die schlimmstenfalls 3-zu-1 ist. Wähle dazu zufällig nicht ein, sondern drei Elemente aus dem Subarray aus und verwende den Median der drei als Pivot (und vertausche ihn mit dem rechten Element wie oben beschrieben). Unter dem Median verstehen wir das Element der drei, dessen Wert in der Mitte liegt. Wir können an dieser Stelle keinen Beweis antreten, aber wenn du den Median von drei zufällig ausgewählten Elementen als Pivot wählst, dann hast du eine 68,75% Wahrscheinlichkeit (11/16), eine 3-zu-1 Partitionierung oder besser zu erhalten. Du kannst noch weiter gehen. Wenn du fünf Elemente zufällig wählst und den Median als Pivot verwendest, erhöht sich die Wahrscheinlichkeit einer 3-zu-1-Partitionierung auf etwa 79,3% (203/256). Wenn du den Median von sieben zufällig ausgewählten Elementen nimmst, steigt die Wahrscheinlichkeit auf etwa 85,9% (1759/2048). Median von neun? Etwa 90,2% (59123/65536). Median von 11? Etwa 93,1% (488293/524288). Siehst du wohin die Reise geht? Natürlich ist es nicht zwangsläufig vorteilhaft, eine große Anzahl von Elementen zufällig auszuwählen und ihren Median zu verwenden, denn dieser Vorgang kostet Rechenzeit und verlangsamt den Algorithmus. Es kommt also auf die richtige Balance an.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.