Skip to content
Snippets Groups Projects
203_Untere_Schranke_Sortieralgorithmen.tex 3.98 KiB
Newer Older
\section{Die untere Laufzeitschranke für vergleichsbasierte Sortieralgorithmen}
Florian Unger's avatar
Florian Unger committed
Wir haben in der analyse von \texttt{mergesort} gesehen, dass die worst-case-Laufzeit $\mathcal{O}(n \log n)$ nicht
unterschreitet. Es ist auch die best-case-Laufzeit von \texttt{quicksort}. Schneller als $\mathcal{O}(n)$ kann ein
Sortieralgorithmus sicherlich nicht sortieren: Er muss ja jeden Input mindestens einmal angeschaut haben. Aber geht es,
im worst-case, schneller als $\mathcal{O}(n \log n)$?

Die Antwort ist - für vergleichsbasierte Algorithmen - nein, und wir werden in diesem Kapitel den Beweis dazu skizzieren.

Doch was ist ein vergleichsbasierter Algorithmus?
Florian Unger's avatar
Florian Unger committed
All unsere bisherigen Sortieralgorithmen verglichen stets zwei Elemente, um ihre entsprechende Reihenfolge untereinander zu
bestimmen. Das impliziert, dass die Elemente eine sogenannte totale Quasiordnung haben mussten;
\begin{definition}[totale Quasiordnung]
  \label{def:totale_Quasiordnung}
  Sei $A$ eine Menge. Eine totale Quasiordnung auf $X$ ist eine binäre Relation $\leq$, für welche gilt:
  \begin{itemize}
    \item $a \leq a$ für alle $a \in A$ (\emph{Reflexifität}).
    \item $a \leq b$ und $b \leq c$ impliziert  $a \leq c$ für alle $a,b,c \in A$ (\emph{Transitivität}).
    \item $a \leq b$ oder $b \leq a$ für alle $a,b \in A$ (\emph{Totalität}).
  \end{itemize}
\end{definition}
Insbesondere erfüllt jede totale Ordnung (also beispielsweise die normale Ordnung auf den ganzen oder reellen Zahlen)
die Axiome der totalen Quasiordnung.
Florian Unger's avatar
Florian Unger committed
Für eine ``echte'' Quasiordnung betrachten wir $X = \{x,y,z\}$, mit $\leq$ definiert durch $y \leq x$, $y \leq z$, $x \leq z$ und $z \leq x$.
Nun sind $x$ und $z$ ``gleich'', wir benutzen das Symbol $x \equiv z$. Formaler aufgeschrieben: $x \leq z  \land  z \leq
x  \Longrightarrow  x \equiv z$.
Florian Unger's avatar
Florian Unger committed

Für ein praktisches Beispiel können wir Spielkarten anschauen, die wir allein nach den numerischen Werten ordnen. Dann
ist mit $x = $ Herz 8, $y = $ Herz 7 und $z = $ Pik 8 klar, dass $x \equiv z$, aber nicht unbedingt $x = z$, wie es bei
einer totalen Ordnung der Fall wäre.

Vergleichsbasierte Sortieralgorithmen vergleichen daher nur immer genau zwei Elemente miteinander. Dies geschieht bei
\texttt{quicksort} beispielsweise in Zeile 4 der Partition, oder bei \texttt{mergesort} in Zeile 4 von \texttt{merge}.


\subsection{Beweisskizze}
Wir betrachten im Folgenden die Anzahl der nötigen Vergleiche für das Sortieren des Inputs. Da der Aufwand eines
vergleichsbasierten Sortieralgorithmus mindestens so schnell wächst wie die Anzahl der nötigen Vergleiche, haben wir damit eine
untere Schranke für den zeitlichen Aufwand.

Der Kontrollfluss eines vergleichenden Sortierverfahrens kann mittels
eines sogenannten \emph{Entscheidungsbaummodells} dargestellt werden.
Florian Unger's avatar
Florian Unger committed
In einem Entscheidungsbaummodell werden alle möglichen und nötigen Entscheidungen dargestellt, um ein
sortiertes lineares Feld zu erhalten. Beispiel: Es liegt eine Sequenz
Florian Unger's avatar
Florian Unger committed
von 3 Zahlen vor $[a_{1},a_{2},a_{3}]$, ganz konkret also möglicherweise $[5,8,2]$. Dann schaut
Florian Unger's avatar
Florian Unger committed
der zugehörige Entscheidungsbaum folgendermaßen aus:

\begin{center}
Florian Unger's avatar
Florian Unger committed
  \includegraphics[scale=0.2]{bilder/Entscheidungsbaummodell}
  \label{fig:Entscheidungsbaum}
\par\end{center}

Florian Unger's avatar
Florian Unger committed
Die Blätter stellen alle möglichen Permutationen des Inputs dar. Die Anzahl der Blätter ist daher gleich $n!$.
Florian Unger's avatar
Florian Unger committed
Das worst-case Verhalten eines Algorithmus entspricht dem längsten Ast im
Entscheidungsbaum, die Anzahl der inneren Knoten ist dabei genau die Anzahl der notwendigen Vergleiche.
Florian Unger's avatar
Florian Unger committed
Ein idealer Sortieralgorithmus enspricht einem vollständigen, ausgeglichenen
Baum. Dadurch wird der längste Ast, also der worst case, minimiert. Die
Höhe beträgt $h \geq \log_2(n!)$. Aber wir haben bereits in einer Übungsaufgabe berechnet, dass gilt:
Florian Unger's avatar
Florian Unger committed
  h \geq \log_2(n!) \in Θ(n \log n).
\]
Also sind wir damit fertig.

\begin{theorem}
Florian Unger's avatar
Florian Unger committed
  Für vergleichsbasierte Sortieralgorithmen liegt die worst-case Laufzeit immer in 
  \[
    Ω(n \log_n).
  \]
Florian Unger's avatar
Florian Unger committed
  \label{theorem:untere_schranke_sortieralgorithmen}
\end{theorem}