prev up next

Previous: Heapsort Up: Sortieren Next: Bucket Sort

Untere Schranke für Sortieren durch Vergleichen

Entscheidungsbaum zur Sortierung von 3 Elementen:
gegeben $A,B,C$


Der Entscheidungsbaum zur Sortierung von $ n $ Elementen hat $ n $! Blätter.


\begin{eqnarray*}
n!\geq n \cdot (n-1)\cdot (n-2)\cdot \ldots \cdot\frac{n}{2}\geq\left(\left(\frac{n}{2}\right)^{\frac{n}{2}}\right)
\end{eqnarray*}



\begin{eqnarray*}
\Rightarrow \log n!&\geq &\log \left(\left(\frac{n}{2}\right)^...
...{2}\\
&\geq&\frac{n}{4}\cdot \log n \mbox{ f\uml {u}r }n \geq 4
\end{eqnarray*}



$\Rightarrow$
Ein binärer Baum mit $n!$ Blättern hat mindestens die Höhe $\frac{n}{4}\cdot \log n$.
$\Rightarrow$
Jeder Sortieralgorithmus, der auf Vergleichen beruht, hat als Laufzeit mindestens
$O(n\cdot \log n)$. Dies ist eine untere Schranke.


prev up next
Previous: Heapsort Up: Sortieren Next: Bucket Sort