Newer
Older
\section{Die untere Laufzeitschranke für vergleichsbasierte Sortieralgorithmen}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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 "uber 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"oglichen und n"otigen 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"orige Entscheidungsbaum folgenderma"sen aus:
\begin{center}
\includegraphics[scale=0.2]{bilder/Entschdeidungsbaummodell}
\par\end{center}
\noindent Die Bl"atter stellen alle m"oglichen Permutationen des Inputs dar. Die Anzahl der Bl"atter ist daher gleich $n!$.
\noindent Das worst-case Verhalten entspricht dem l"angsten Ast im
Entscheidungsbaum (Anzahl der inneren Knoten = Anzahl der Vergleiche).
Der ideale Sortieralgorithmus enspricht einem vollst"andigen, ausgeglichenen
Baum. Dadurch wird der l"angste Ast ( = worst case) minimiert. Die
H"ohe betr"agt $h\geq\log(n!).$ Mit Hilfe der Stirling-Approximation
$n!>(\frac{n}{e})^{n}$ erh"alt 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"ur die Anzahl der im worst case zum Sortieren notwendigen Vergleiche
(und somit f"ur 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"ur \textbf{\underbar{jede}}
Eingabefolge in $O(n\cdot\log\: n)$ sortiert. Zum Beispiel sind \emph{MERGESORT}
und \emph{HEAPSORT} worst-case optimal.