Nächste Seite: Weitere Sortierverfahren Aufwärts: Hauptseite Algorithmen Vorherige Seite: Mastertheorem Inhalt

Ableitung der untersten Schranke von Sortierverfahren $n\log(n)$

Wir können eine Entscheidungsbaum erzeugen, der anhand von Vergleichen auf die richtige Permutation der Eingabe schließt. Für

Zahlen gibt es

Permutationen.

Jeder Binärbaum der Höhe

hat höchstens $2^{h}$ Blätter. Es gilt

$\begin{displaymath}2^{h}\geq n!\Rightarrow h\geq \log(n!)\end{displaymath}$

Da $n!\geq (\frac{n}{e})^{n}$ können wir $\log(n!)$ folgendermaßen abschätzen

$\begin{displaymath}\log n!\geq \log\left(\frac{n}{e}\right)^{n}=n\log\left(\frac{n}{e}\right)=n\log(n)-n\log(e)\end{displaymath}$

$\Rightarrow \Omega (n\log(n))$
Somit haben wir eine Baumtiefe von mindestens $n\log(n)$ , was die untere Schranke für Sortierverfahren ist.