%% -*- mode: latex; TeX-master: "informatik.tex"; -*-

\begin{slide}{Komplexität von Problemen}

\kopf{$ $Id: schrank.tex,v 1.1 2006-10-09 13:24:19 waldmann Exp $ $}

Wie schwer ist ein (algorithmisches) Problem?

Wieviel Ressourcen braucht \emph{jeder} Algorithmus,
der das Problem löst?

Satz: Für \emph{jedes} Sortierververfahren für $n$ Elemente
gibt es eine Eingabe, 
für die das Verfahren $\ge \log_2 (n!)$ Vergleiche ausführt.

Beweis: es gibt $n!$ Permutationen, unter denen genau eine zu finden ist.
Durch Elementvergleiche können wir in jedem Schritt
die Anzahl der Möglichkeiten bestenfalls halbieren.

Damit brauchen wir $\ge \log_2(n!)$ Vergleiche.

\bigskip

Aufgabe: Werteverlauf dieser Funktion ausrechnen
und mit bekannten Sortierverfahren/-Netzen vergleichen.

\newpage

Abschätzung des Wachstums: $\log_2(n!) \approx n \log n$

Folgerung: Sortieren hat eine Komplexität von wenigstens
$n \log n$. (D. h. mehr als linear, 
aber weniger als quadratisch.)

Folgerung: Sortieren durch binäres Einfügen ist optimal 
(durch lineares Einfügen nicht).
\end{slide}
