\documentstyle[12pt,A4,german]{article}
\begin{document}
\begin{center}
\Large
Notationen f"ur asymptotisches Verhalten
\end{center}
\normalsize
\section{Vorbemerkungen} 
\begin{itemize}
\item
Die hier aufgef"uhrten Definitionen stimmen mit denen in chapter 2 im Buch von 
{\sc Cormen/Leiser\-son/Rivest} "uberein. Man beachte, da"s in der sonstigen
Literatur gelegentlich leicht abweichende Definitionen verwendet werden,
insbes. bei $\Omega$, $\omega$ und $\Theta$. Nachlesenswert ist auch
section 2.1 in {\sc Brassard/Bratley}.
\item 
Die hier aufgef"uhrten Definitionen beziehen sich auf das Verhalten von
Funktionen $f,g \,:\, {\bf N} \rightarrow {\bf R}$ f"ur 
$n \rightarrow \infty$. Normalerweise nimmt man als Definitionsbereich
der Funktionen $f,g$ die Menge aller reellen Zahlen {\bf R}
(oder ein Teilintervall) und kann dann auch von asymptotischen Verhalten f"ur 
$n \rightarrow a$ mit $a \in {\bf R}$ sprechen. Die Definitionen "ubertragen 
sich sinngem"a"s.
\item
Damit die nachfolgenden Definitionen sinnvoll sind, sollten die an ihnen
beteiligten Funktionen {\em asymptotisch nichtnegativ} sein, d.h.
$f(n), g(n) \geq 0$ f"ur alle hinreichend gro"sen $n \in {\bf N}$.
Das ist bei unseren Anwendungen von Natur aus der Fall. W"are das
nicht so, h"atte man sich noch mit Absolutbetr"agen herumzuschlagen.
\item 
Anstelle der ``"ublichen'' Schreibweise $f(n) = O(g(n))$ usw. wird hier die
logisch saubere Notation $f(n) \in O(g(n))$, die klar zum Ausdruck bringt, da"s
$O(g(n)$ eine Klasse von Funktionen (mit bestimmten Eigenschaften) ist,
und da"s $f(n)$ zu dieser Klasse geh"ort. Noch gr"o"sere logische
Sorgfalt w"urde empfehlen, statt ``die Funktion $f(n)$'' etwa die
$\lambda$-Notation $\lambda\,n \,. \,f(n)$ zu verwenden.
\end{itemize}
\section{Definitionen}
\begin{itemize}
\item
$f(n) \in O(g(n))$ : `` $g(n)$ ist {\em asymptotische obere Schranke} f"ur $f(n)$ ''  
\[
\exists c,n_0 > 0 ~\forall n \geq n_0 ~:~0 \leq f(n) \leq c \cdot g(n)
\]
d.h. $f(n)$ ist von einer hinreichend gro"sen Stelle $n_0$ an durch ein 
konstantes Vielfaches von $g(n)$ nach oben beschr"ankt.
\item
$f(n) \in \Omega(g(n))$ : `` $g(n)$ ist {\em asymptotische untere Schranke} f"ur $f(n)$ ''  
\[
\exists c,n_0 > 0 ~\forall n \geq n_0 ~:~0  \leq c \cdot g(n) \leq f(n)
\]
d.h. $f(n)$ ist von einer hinreichend gro"sen Stelle $n_0$ an durch ein 
konstantes Vielfaches von $g(n)$ nach unten beschr"ankt.
\item
$f(n) \in \Theta(g(n))$ : `` $g(n)$ hat gleiche Wachstumsordnung wie $f(n)$ ''  
\[
f(n) \in O(g(n)) ~\wedge f(n) \in \Omega(g(n))
\]
Anschaulich: von einer hinreichend gro"sen Stelle $n_0$ an
bewegt sich der Graph von $f$ in einem ``Schlauch'', der von zwei
konstanten Vielfachen von $g$ gebildet wird.
\item
$f(n) \in o(g(n))$ : `` $f(n)$ hat kleinere Wachstumsordnung als $g(n)$ ''  
\[
\forall c >0~\exists n_0 > 0 ~\forall n \geq n_0 ~:~0 \leq f(n) < c \cdot g(n)
\]
d.h. $f(n)$ w"achst langsamer als alle konstanten Vielfachen von $g(n)$
\item
$f(n) \in \omega(g(n))$ : `` $f(n)$ hat gr"o"sere Wachstumsordnung als $g(n)$ ''  \[
\forall c>0~\exists n_0 > 0 ~\forall n \geq n_0 ~:~0  \leq c \cdot g(n) < f(n)
\]
d.h. $f(n)$ w"achst schneller als alle konstanten Vielfachen von $g(n)$
\item
$f(n) \sim g(n)$ oder $f(n) \approx g(n)$ : `` $f(n)$ und $g(n)$ sind 
asymptotisch "aquivalent''
\[
\lim_{n \rightarrow \infty} {f(n) \over g(n) } = 1
\]
\end{itemize}
\section{Eigenschaften}
\begin{itemize}
\item
$O,\Omega,\Theta,o,\omega$ und $\sim$ sind {\em transitiv} in dem Sinne
\[
f(n) \in O(g(n))~\wedge~ g(n) \in O(h(n))~\Rightarrow~
f(n) \in O(h(n))~~~\hbox{usw.}
\]
\item
$O,\Omega,\Theta$ und $\sim$ sind {\em reflexiv} in dem Sinne
\[
f(n) \in O(f(n))~~~\hbox{usw.}
\]
\item
$\Theta$ und $\sim$ sind {\em symmetrisch} in dem Sinne
\[
f(n) \in \Theta(g(n)) ~\Rightarrow~ g(n) \in \Theta(f(n))
\]
\item
\begin{eqnarray*}
f(n) \in O(g(n)) 
&~\Leftrightarrow~& 
g(n) \in \Omega(f(n)) \\
f(n) \in o(g(n)) 
&~\Leftrightarrow~&
g(n) \in \omega(f(n))
\end{eqnarray*}
\item
f"ur asymptotisch nichtnegative Funktionen:
\begin{eqnarray*}
f(n) \in o(g(n))
&~\Leftrightarrow~&
\lim_{n \rightarrow \infty} \, {f(n) \over g(n)} = 0 \\
f(n) \in \omega(g(n))
&~\Leftrightarrow~&
\lim_{n \rightarrow \infty} \, {f(n) \over g(n)} = \infty
\end{eqnarray*}
\end{itemize}
\section{Bezeichnungen}
Man nennt das Wachstumsverhalten einer Funktion $f(n)$
\begin{eqnarray*}
\hbox{\em konstant} &\hbox{falls}& f(n) \in \Theta(1) \\
\hbox{\em logarithmisch} &\hbox{falls}& f(n) \in \Theta(\log n) \\
\hbox{\em polylogarithmisch} &\hbox{falls}& f(n) \in \Theta((\log n)^c) ~\hbox{mit}~c \geq 1\\
\hbox{\em sublinear} &\hbox{falls}& f(n) \in \Theta(n^c)~\hbox{mit}~0<c <1 \\
\hbox{\em linear} &\hbox{falls}& f(n) \in \Theta(n) \\
\hbox{\em quadratisch} &\hbox{falls}& f(n) \in \Theta(n^2) \\
\hbox{\em kubisch} &\hbox{falls}& f(n) \in \Theta(n^3) \\
\hbox{\em polynomial} &\hbox{falls}& f(n) \in \Theta(n^c) ~\hbox{mit}~c \geq 1 \\
\hbox{\em exponentiell} &\hbox{falls}& f(n) \in \Theta(c^n) ~\hbox{mit}~c > 1\\
\end{eqnarray*}
Damit wird noch nicht alles ausgesch"opft: beispielsweise gibt es
interessante Funktionen, die schneller wachsen als jedes Polynom,
d.h. $f(n) \in \Omega(n^c)$ f"ur jedes $c>0$, aber langsamer als jede 
Exponentialfunktion, d.h. $f(n) \in o(d^n)$ f"ur jedes $d>1$.
Beispiele sind
$e^{\log^2n}$ und $e^{\sqrt{n}}$. Solche Funktionen haben 
{\em subexponentielles} oder {\em schwach-exponentielles} Wachstum.
Andereseits w"achst beispielsweise $n!$ schneller als jede
Exponentialfunktion, denn es gilt {\sc Stirling}s Formel
\[
 n! \sim \left({n \over e}^n\right)\,\sqrt{2 n  \pi}
\]
Deren Wachstum, wie auch das von $2^{n^2}$, ist {\em superexponentiell}.
Es bereitet nat"urlich keine mathematischen Schwierigkeiten, Funktionen mit noch
st"arkerem Wachstum anzugeben. F"ur den hier betrachteten Bereich der Komplexit"atsanalyse spielen diese aber kaum eine Rolle.
\section{Beispiele}
(wird noch erg"anzt)
\end{document}