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

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

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

Wie gut ist ein Algorithmus? 

\begin{itemize} \itemsep 0pt
\item
  Ressourcen-Verbrauch (Rechenzeit/Speicherplatz/\dots)?
\item
  Für \emph{eine} spezielle Eingabe? ---
  Besser: Mengen von ähnlichen (= gleich großen) Eingaben betrachten.
\item
  Ressourcen für besten, mittleren, schlechtesten Fall.
\item
  Betrachten der Verbrauchsfunktion:

  bildet Eingabegröße ab auf (minimale, durchschnittliche, maximale) Kosten
  aller Rechnungen für alle Eingaben dieser Größe
\newpage
\item
  Maschinen-unabhängige Aussagen
  durch Betrachtung des (asymptotischen) \emph{Wachstums}, d. h. ignoriere:
  \begin{itemize}
  \item
    Unregelmäßigkeiten für kleine Eingaben
  \item
    konstante Faktoren (für alle Eingaben)
  \end{itemize}
\end{itemize}

Beispiele: alle linearen Funktionen wachsen ähnlich,
alle quadratischen Funktionen wachsen ähnlich, etc.

\end{slide}

\begin{slide}{Komplexität -- Beispiel}

Sortieren durch \emph{lineares} Einfügen 
(bzw. entsprechendes Netzwerk)
benötigt für $n$ Elemente 
\[ 0 + 1 + 2 + \ldots + (n-1) = (n-1)n/2 \]
Vergleiche.

Egal, auf welchem Rechner wir das ausführen,
die Laufzeit wird \emph{immer} eine quadratische Funktion
der Eingabegröße sein.

D. h. Eingabegröße verdoppeln $\to$ vierfache Laufzeit,
verdreifachen $\to$ neunfache, usw.

Schnelleren Prozessor zu kaufen lohnt sich kaum,
man gewinnt damit nur einen konstanten Faktor.
Viel wirksamer sind bessere Algorithmen!
\end{slide}
