Newer
Older
\section{Die untere Laufzeitschranke für vergleichsbasierte Sortieralgorithmen}
Viele verwendete schnelle Sortierverfahren (z.B.: \emph{MERGESORT},
\emph{HEAPSORT}) besitzen eine Laufzeit von $O(n\log n)$. Die Frage,
die sich dabei stellt, lautet: Geht es besser?
\noindent Man kann beweisen, dass jedes Sortierverfahren, das mittels
Vergleichen arbeitet%
\footnote{ D.h., bei dem die Information über die korrekte Anordnung der Elemente dadurch gewonnen wird, dass jeweils einzelne Elemente direkt miteinander verglichen
werden.%
}, mindestens $c\cdot n\log n$ Vergleiche im \textbf{worst
case} braucht (wobei $c>0$ und konstant ist).
\subsection{Herleiten der unteren Schranke $\Omega\left(n\log n\right)$ }
Der Kontrollfluss eines vergleichenden Sortierverfahrens kann mittels
eines sogenannten \emph{Entscheidungsbaummodells} dargestellt werden.
Darin scheinen alle möglichen und nötigen Entscheidungen auf, um ein
sortiertes lineares Feld zu erhalten. Beispiel: Es liegt eine Sequenz
von 3 Zahlen vor $<a_{1},a_{2},a_{3}>$ (z.B. $<5,8,2>$). Dann schaut
der zugehörige Entscheidungsbaum folgendermaßen aus:
\begin{center}
\includegraphics[scale=0.2]{bilder/Entschdeidungsbaummodell}
\par\end{center}
\noindent Die Blätter stellen alle möglichen Permutationen des Inputs dar. Die Anzahl der Blätter ist daher gleich $n!$.
\noindent Das worst-case Verhalten entspricht dem längsten Ast im
Entscheidungsbaum (Anzahl der inneren Knoten = Anzahl der Vergleiche).
Der ideale Sortieralgorithmus enspricht einem vollständigen, ausgeglichenen
Baum. Dadurch wird der längste Ast ( = worst case) minimiert. Die
Höhe beträgt $h\geq\log(n!).$ Mit Hilfe der Stirling-Approximation
$n!>(\frac{n}{e})^{n}$ erhält man:
\[
h\geq\log\left(\frac{n}{e}\right)^{n}=n\cdot\log n-n\cdot\log e=\Omega(n\cdot\log n)\]
\bigskip{}
\noindent $\Omega(n\cdot\log\: n)$ ist die \textbf{untere
Schranke} für die Anzahl der im worst case zum Sortieren notwendigen Vergleiche
(und somit für die worst case Laufzeit vergleichender Sortierverfahren).
\subsection{worst-case optimal}
Im Zusammenhang der unteren Schranke kann einen Sortieralgorithmus
als \textbf{worst-case optimal} bezeichnen, wenn er für \textbf{\underbar{jede}}
Eingabefolge in $O(n\cdot\log\: n)$ sortiert. Zum Beispiel sind \emph{MERGESORT}
und \emph{HEAPSORT} worst-case optimal.