Quicksort: Unterschied zwischen den Versionen
Thomas (Diskussion | Beiträge) |
Thomas (Diskussion | Beiträge) |
||
| Zeile 99: | Zeile 99: | ||
Wenn wir die Partitionierungszeiten für jede Ebene aufsummieren, erhalten wir nach der [[Arithmetische-reihe|gauschen Summenformel]]: | 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> | <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>. | 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>. | ||
== Best Case == | == Best Case == | ||