next up previous
Nächste Seite: Komplexitšt von Problemen Aufwärts: Berechenbarkeit, Komplexitšt (24. 10. Vorherige Seite: Merge-Sort (Merge)

Merge-Sort (Komplexitšt)

Anzahl der Vergleiche?

$\displaystyle T(1)=0, T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2\rceil) + (n-1) $

Beispiele:

\begin{displaymath}
\begin{array}{c\vert cccccccccc}
n & 1 & 2 & 3 & 4 & 5 & 6 ...
...\hline
T(n)& 0 & 1 & 3 & 5 & 8 & 11 & 14 & 17 & 21
\end{array}\end{displaymath}

‹bung: beweise durch Induktion $T(2^k) = 1 + (k-1) \cdot 2^k$.

Mit $n = 2^k$, also $k = \log_2 n$ folgt $T(n) \approx n \log_2 n$.

D. h. Merge-Sort ist asymptotisch besser als Bubble-Sort.



Johannes Waldmann 2004-01-30