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.

Ψ Die Informatikseite