Quicksort: Unterschied zwischen den Versionen
Keine Bearbeitungszusammenfassung |
|||
| Zeile 220: | Zeile 220: | ||
<math>c \cdot n + c \cdot (n - 1) + c \cdot (n - 2) + \dots + c \cdot 2</math> | <math>c \cdot n + c \cdot (n - 1) + c \cdot (n - 2) + \dots + c \cdot 2</math> | ||
Wir klammern <math>c</math> aus und erkennen die bekannte [[ | Wir klammern <math>c</math> aus und erkennen die bekannte [[Arithmetische_Reihe|Gaußsche Summenformel]]: | ||
<math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math> | <math>c \cdot (n + (n-1) + (n-2) + \dots + 2) \approx c \cdot \frac{n(n+1)}{2} = \frac{c}{2}n^2 + \frac{c}{2}n</math> | ||