Quicksort: Unterschied zwischen den Versionen

@@ Zeile 90: / Zeile 90: @@
     }
 </syntaxhighlight>
+== Laufzeitanalyse ==
+=== Worst-Case ===
+[[Datei:Baum N-Ebenen.png|mini]]
+Betrachten wir zunächst die Worst-Case-Laufzeitanalyseaufzeit. Angenommen, wir haben wirklich Pech und die Partitionsgrößen sind wirklich unausgeglichen. Angenommen, der von der Partitionsfunktion ausgewählte Drehpunkt ist immer entweder das kleinste oder das größte Element im Subarray für n-Elemente. Dann enthält eine der Partitionen keine Elemente und die andere Partition enthält n-1 Elemente - alle außer dem Pivot. Die rekursiven Aufrufe erfolgen also auf Subarrays der Größen 0 und n-1.
+In diesem Szenario benötigt [[Rekursion|rekursive]] Aufruf von n-1  Elementen c* (n - 1) für eine Konstante c. Dies Konstante c repräsentiert die Benötigte Zeit für eine Operation wie einen Aufruf oder einen Vergleich. Für n-2 Elemente werden die Zeit c*(n-2) benötigt und so weiter (siehe Abbildung).
+Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]:
+<math>cn+c(n−1)+c(n−2)+⋯+2c = c(n+(n−1)+(n−2)+⋯+2) =c((n+1)(n/2)−1)</math>
+Im Rahmend er Laufzeitanalyse ignorieren wir Terme niedriger Ordnung und konstante Koeffizienten. In der Big-Θ-Notation folgt hieraus die Worst-Case-Laufzeit von QuickSort <math> O(n^2)</math>.