\documentstyle[12pt,A4,german]{article} \begin{document} %\begin{center} \section{L"osungstypen f"ur die {\em divide-and-conquer}-Rekursion $t(n) = a \cdot t(n/b) + f(n)$} %\end{center} \subsection{Vorbemerkung} Rekursiongleichungen dieses Typs werden in vielen B"uchern "uber Komplexit"atsanalyse behandelt. Besonders herauszuheben ist die sehr gr"undliche Abhandlung in den Abschnitten 4.3/4.4 von {\sc Cormen/Leiserson/Rivest}, wo dies als ``Master Method'' bezeichnet wird. Dort wird allerdings der explizite Bezug auf den Konvergenzradius von Potenzreihen vermieden. \subsection{Die anschauliche Bedeutung solcher Rekursionen} In vielen F"allen f"uhrt die Analyse von {\em divide-and-conquer}-Algorithmen auf Rekursionsgleichungen des folgenden Typs: \begin{equation}\label{one} t(n) = a \cdot t(n/b) + f(n)~~~,~~~ t(1) = f(1) > 0 \end{equation} Hierbei soll $b$ ganz und $\geq 2$ sein, $a > 0$ und $f(n) \geq 0$. Die anschauliche Bedeutung dieser Rekursion: $t(n)$ beschreibt die Kosten f"ur die Ausf"uhrung eines Algorithmus bei Problemgr"o"se $n$. Probleminstanzen dieser Gr"o"se werden bearbeitet, indem sie in $a$ Teilprobleme (gleichen Typs) der Gr"o"se $n/b$ zerlegt werden (und dies Vorgehen wird rekursiv weitergef"uhrt, bis Probleme der Gr"o"se 1 erreicht werden).\footnote{ In der Praxis ist es oft so, da"s man diese rekursive Bearbeitung nicht bis zur kleinstm"oglichen Problemgr"o"se treibt, sondern vorher schon auf (nicht-rekursive) Algorithmen umschaltet, die f"ur kleine Problemgr"o"sen besser sind als das rekursive Verfahren. F"ur die Resultate, die hier interessieren, hat das keine Bedeutung.} Mit $f(n)$ wird der {\em overhead} beschrieben, der bei dieser Zerlegung in Teilprobleme und der Synthese des Ergebnisses aus den L"osungen f"ur die Teilprobleme ben"otigt wird (vgl. etwa die Prozedur {\em merge} bei {\em mergesort}). Das Ziel der Untersuchung von Rekursionen wie (\ref{one}) wird es sein, Informationen "uber das Wachstumsverhalten der L"osung $t(n)$ in Abh"angigkeit von $a,b$ und der {\em overhead}-Funktion $f(n)$ zu erhalten. Die Erfahrung lehrt, da"s man oft "uber das Verhalten von $f(n)$ nur ungenaue Kenntnis hat, da"s aber auch bei expliziter Kenntnis von $f(n)$ eine explizite L"osung f"ur $t(n)$ nicht m"oglich ist, aus der man deren Wachstumsverhalten direkt ablesen k"onnte. Daher mu"s es das Ziel sein, auch aus ungef"ahrer Kenntnis der Funktion $f(n)$, also beispielsweise "uber deren Wachstumsverhalten im Sinne einer $\Theta$-Aussage, entsprechende Aussagen "uber die L"osungsfunktion $t(n)$ zu gewinnen. Es macht zun"achst nur Sinn, diese Rekursion (\ref{one}) f"ur Argumente zu betrachten, die Potenzen von $b$ sind --- allerdings bleiben alle Aussagen richtig, wenn $n \mapsto t(n)$ {\em monoton steigend} ist. Man setzt also \[ t_m := t(b^m) ~~,~~ f_m := f(b^m)~~,~~m=0,1,2,3,\ldots \] und fa"st diese Zahlen zusammen, indem man sie als Koeffizienten in Potenzreihen steckt : \[ \tau(z) := \sum_{m \geq 0} t_m \, z^m ~~,~~ \phi(z) := \sum_{m\geq 0} f_m \, z^m \] \subsection{Warum Potenzreihen ?} Es ist eine fundamentale Einsicht der Analysis, da"s ein enger Zusammenhang zwischen dem Konvergenzradius $K_g$ einer Potenzreihe $g(z) = \sum_{n \geq 0} g_n \, z^n$ und dem Wachstumsverhalten der Koeffizientenfolge $(g_n)_{n \geq 0}$ besteht: \[ K_g^{-1} = \overline{\lim_{n \rightarrow \infty}} | g_n |^{1/n} \] was man f"ur unsere Zwecke besser so ausdr"uckt\footnote{ Die Bezeichnung $\overline{\lim}$ liest der Mathematiker als {\em limes superior} und schreibt daf"ur oft auch {\em lim\,sup}. Jede Folge $(x_n)_{n \geq 0}$ von reellen Zahlen hat einen (eindeutig bestimmten) {\em limes superior}, der allerdings auch unendlich sein kann. In unserer Situation entspricht das einem Konvergenzradius $K = 0$.}: \begin{quote} f"ur alle $\epsilon > 0$ gilt \[ \left( K_g^{-1} - \epsilon \right)^n <_{i.o.} | g_n | <_{a.e.} \left( K_g^{-1} + \epsilon \right)^n \] wobei die linke Ungleichung f"ur unendlich viele $n$ gilt (i.o. = {\em infinitely often}), w"ahrend die rechte Ungleichung f"ur fast alle $n$ gilt (a.e. = {\em almost everywhere}). \end{quote} Das hei"st also: der reziproke Konvergenzradius $K_g^{-1}$ beschreibt den {\em exponentiellen} Anteil am Wachstumsverhalten von $(g_n)_{n \geq 0}$. (N.B. Dies gilt auch, falls $K_g = 0$ oder $K_g = \infty$ ist: dann w"achst $(g_n)_{n \geq 0}$ st"arker bzw. schw"acher als jede Exponentialfunktion.) Noch anders ausgedr"uckt: \[ \forall n ~:~ | g_n | = K_g^{-n} \cdot \tilde{g}_n \] wobei $n \mapsto \tilde{g}_n$ eine Folge ist, die den {\em subexponentiellen} Anteil am Wachstumsverhalten von $(g_n)_{n \geq 0}$ beschreibt: \[ \forall \epsilon > 0 ~:~ (1 - \epsilon)^n <_{i.o.} | \tilde{g}_n | <_{a.e} (1+ \epsilon)^n \] (d.h. die Potenzreihe $\tilde{g}(z) = \sum_n \tilde{g}_n \, z^n$ hat Konvergenzradius $K_{\tilde{g}} = 1$). Eine leichte Rechnung zeigt, da"s die Rekursionsbeziehung (\ref{one}) "aquivalent ist zu der funktionalen Beziehung \begin{equation}\label{two} \tau(z) = {1 \over 1-az} \cdot \phi(z) \end{equation} und dies wiederum ist "aquivalent zu der Summendarstellung \begin{equation}\label{three} t_m = \sum_{i=0}^m f_i \, a^{m-i}~~~~(m \geq 0) \end{equation} \subsection{Fallunterscheidung und L"osungstypen} Die funktionale Darstellung (\ref{two}) sagt uns sofort, da"s drei verschiedene Situationen auftreten k"onnen --- beachte dabei, da"s $1/a$ der Konvergenzradius der geometrischen Reihe $1/(1-az) = \sum_{n \geq 0} (az)^n$ ist: \begin{itemize} \item $K_{\phi} > 1/a$, d.h. es wird $K_{\tau} = \min(K_{\phi},1/a) = 1/a$ sein und das exponentielle Wachstum von $(t_m)_{m \geq 0}$ wird durch $a^m$ bestimmt. Heuristisch bedeutet dies, da"s die overhead-Kosten, ausgedr"uckt durch die Funktion $\phi(z)$, am Wachstum der Gesamtkosten nur einen subexponentiellen Anteil haben, also f"ur gro"se Probleminstanzen zu vernachl"assigen sind. Beachte: $a^m$ gibt die Anzahl der schlie"slich zu bearbeitenden Elementarprobleme der Gr"o"se 1 an, und die Gesamtkosten verhalten sich im wesentlichen proportional zu dieser Zahl. \item $K_{\phi} = 1/a$, d.h. es wird auch hier $K_{\tau} = \min(K_{\phi},1/a) = 1/a$ sein, und das exponentielle Wachstum von $(t_m)_{m \geq 0}$ wird also durch $a^m$ bestimmt --- allerdings mit dem Unterschied, da"s hier auch die overhead-Kosten zu den Gesamtkosten wesentlich beitragen. \item $K_{\phi} < 1/a$, d.h. es wird $K_{\tau} = \min(K_{\phi},1/a) = K_{\phi}$ sein und das exponentielle Wachstum von $(t_m)_{m \geq 0}$ wird durch $K_{\phi}^{-m}$ bestimmt. Hier gehen die Gesamtkosten fast ausschlie"slich zu Lasten des overheads. \end{itemize} Nach diesem qualitativen "Uberblick nun die genauere Diskussion der L"osungstypen: \begin{enumerate} \item Der Fall $K_{\phi} > 1/a$: \newline Dieser Fall tritt beispielsweise ein, wenn $f(n) \in \Theta(n^k)$ ist und $a > b^k$. In jedem Fall gilt: \[ t_m = \sum_{i=0}^m f_i \, a^{m-i} = a^m \cdot \sum_{i=0}^m f_i \, {1 \over a^i} \] und es ist \[ f_0 \leq \sum_{i=0}^m f_i \, {1 \over a^i} \leq \phi({1 \over a}) \in {\bf R} \] da ja $\phi(z)$ f"ur $z=1/a$ konvergiert. Also gilt \[ t_m \in \Theta(a^m) \] und, wenn man dies durch $n = b^m$ ausdr"uckt: \[ t(n) = t(b^m) = t_m \in \Theta(a^m) = \Theta(n^{\log_b a}) \] \item Der Fall $K_{\phi} < 1/a$: \newline Betrachten wir hier den ``typischen'' Fall, da"s $f(n) \in \Theta(n^k)$ ist mit $a < b^k$. Aus einer Absch"atzung $f(n) \leq c \cdot n^k$, d.h. $f_m \leq c \cdot b^{mk}$, wird mit Hilfe von (\ref{three}): \[ t_m \leq c \cdot b^{mk} \sum_{i=0}^m \left({a \over b^k}\right)^i \] und die rechts stehende geometrische Reihe konvergiert f"ur $m \rightarrow \infty$. Daher also \[ t_m \in O((b^m)^k)~~,~\hbox{also}~~t(n) \in O(n^k) \] Andererseits ist $t_m \geq f_m$, also insgesamt, wenn man es durch $n = b^m$ ausdr"uckt: \[ t(n) \in \Theta(n^k) \] Ist $f$ nicht von der angegebenen Form, so muss man eventuell genauer untersuchen, so wie das bei dem n"achsten Fall geschieht: \item Der Fall $K_{\phi} = 1/a$: \newline Dies ist der ``kritische'' Fall. Schreiben wir hier zun"achst einmal \[ f_m = a^m \cdot \tilde{f}_m~~,~~\hbox{wobei} ~~\overline{\lim_{m \rightarrow \infty}} \tilde{f}_m^{1/m} = 1 \] d.h. $\tilde{f}_m$ beschreibt den subexponentiellen Anteil des Verhaltens von $f_m$. Dann ist also \[ t_m = \sum_{i=0}^m f_i \, a^{m-i} = a^m \sum_{i=0}^m \tilde{f}_i \] und der subexponentielle Anteil des Verhaltens von $t_m$ wird durch die rechts stehende Summe beschrieben. Betrachten wir den Fall, wo $b^k = a$ ist und \[ f(n) = c \cdot n^k \cdot \left( \log_b n \right)^q ~~~\hbox{f"ur}~n > 1, q ~\hbox{reell} \] Dann ist also \[ f_m = c \cdot b^{mk} \cdot m^q~~~\hbox{d.h.}~~ \tilde{f}_m = c \cdot m^q ~~~(m > 0) \] Hier sind wiederum drei F"alle zu unterscheiden: \begin{enumerate} \item Fall $q < -1$ : \newline In diesem Fall konvergiert $ \sum_{i=0}^{m} \tilde{f}_i = c \left(f(1) + \sum_{i=1}^{m} i^q \right) $ f"ur $m \rightarrow \infty$ und daher \[ t(n) =t(b^m) \in \Theta(a^m) = \Theta(n^{\log_b a}) \] \item Fall $q=-1$ : \newline In diesem Fall hat man es mit $f(1) + \sum_{i=1}^{m} \tilde{f}_i = f(1) + c \, H_m \approx c' \, \log m $ zu tun, und deshalb: \[ t(n) \in \Theta(a^m \, \log m) = \Theta \left( n^{\log_b a} \log \log_b n\right) \] \item Fall $q > -1$ : \newline In diesem Fall verh"alt sich $\sum_{i=0}^m \tilde{f}_m = f(1) + c \,\sum_{i=1}^m i^q$ wie ein $\Theta(m^{q+1})$ und daher \[ t(n) \in \Theta(a^m \, m^{q+1}) = \Theta \left( n^{\log_b a} \left(\log_b n \right)^{1+q} \right) \] \end{enumerate} \end{enumerate} \subsection{Beispiele} Hier nun einige Beispiele: \begin{eqnarray*} t(n) = t(n/2) + c & \Rightarrow & t(n) \in \Theta( \log n) \\ t(n) = 2 \, t(n/2) + c \,n & \Rightarrow & t(n) \in \Theta(n \log n) \\ t(n) = 2 \, t(n/2) + c \, n^2 & \Rightarrow & t(n) \in \Theta( n^2) \\ t(n) = 4 \, t(n/2) + c \, n^2 & \Rightarrow & t(n) \in \Theta(n^2 \log n) \\ t(n) = 7 \, t(n/2) + c \, n^2 & \Rightarrow & t(n) \in \Theta( n^{\log_2 7}) \\ t(n) = 2 \, t(n/2) + \log n & \Rightarrow & t(n) \in \Theta( n) \\ t(n) = 3 \, t(n/2) + n \log n & \Rightarrow & t(n) \in \Theta(n^{\log_2 3}) \\ t(n) = 2 \, t(n/2) + n \log n & \Rightarrow & t(n) \in \Theta( n \log^2 n) \\ t(n) = 5 \, t(n/2) + (n \log n)^2 & \Rightarrow & t(n) \in \Theta( n^{\log_2 5}) \end{eqnarray*} \section{Einige weitere Beispiele und Bemerkungen zu Potenzreihen und dem Wachstumsverhalten der Koeffizienten} \subsection{Beispiele} \begin{enumerate} \item Geometrische Reihe: \[ g(z) = 1/(1-a\,z) = \sum_{n \geq 0} (a \, z)^n ~\hbox{mit}~ a > 0 \] Hier ist $K_g = 1/a$ und der subexponentielle Anteil $\tilde{g}_n$ an der Koeffizienten $g_n = a^n$ ist konstant = 1. Betrachtet man beispielweise das Quadrat von $g(z)$: \[ g(z)^2 = \sum_{n \geq 0} g_n^{(2)} \, z^n = \sum_{n \geq 0} (n+1)\,a^n z^n \] so sieht man, da"s auch $g(z)^2$ den Konvergenzradius $K_{g^2}=1/a$ hat, denn $g_n^{(2)} = (n+1)\,a^n$ w"achst exponentiell wie $a^n$. Der subexponentielle Anteil ist hier $\tilde{g}_n^{(2)}= 1+n$. \item Logarithmische Reihe: \[ h(z) = - \log (1-a\,z) = \sum_{n \geq 1} (a \, z)^n/n ~\hbox{mit}~ a > 0. \] Hier sind die Reihenkoeffizienten $h_n = a^n/n$, der Konvergenzradius ist, wie bekannt, $K_h = 1/a$, und der subexponentielle Anteil betr"agt $\tilde{h}_n = 1/n$. \item {\sc Catalan}-Zahlen (sehr wichtiges Beispiel): \[ c(z) = \sum_{n\geq 0} c_n \,z^n = \left(1 - \sqrt{1-4\,z}\right)/2z \] Die Koeffizienten von $c(z)$, die sogenannten {\sc Catalan}-Zahlen $c_n, n\geq 0$, verdanken ihre Bedeutung f"ur die Informatik der Tatsache, da"s sie die Anzahl der vollst"andigen bin"aren B"aume mit $n$ inneren Knoten (also $n+1$ \"au"seren Knoten) angeben. Eine intime Kenntnis von Eigenschaften dieser Zahlen $c_n$ ist f"ur Komplexit"atsanalysen von Algorithmen, die sich mit B"aumen befassen, unerl"asslich. Unter den vielen anderen Bedeutungen dieser Zahlen, die deren Wichtigkeit unterstreichen, findet man die Anzahl der korrekten Klammerausdr"ucke "uber einem Alphabet, bestehend aus einem Klammerpaar. Anders ausgedr"uckt: $c_n$ ist die Anzahl der W"orter der L"ange $2 n$ der sogenannten {\sc Dyck}-Sprache, also der wichtigsten kontextfreien Sprache "uberhaupt. Es ist nicht schwer, aus einer dieser ``kombinatorischen'' Bedeutungen von $c_n$ eine rekursive Beziehung herzuleiten: \[ c_n = \sum_{i=0}^{n-1} c_i \cdot c_{n-i-1}~~~(n>0),~~~c_0 = 0 \] die "aquivalent ist zu der Funktionalgleichung \[ c(z) = 1+ z \cdot c(z)^2 \] Da dies eine harmlose quadratische Gleichung ist, kann man sie explizit l"osen: \[ c(z) = {1 - \sqrt{1-4\,z} \over 2\,z} \] und die Reihentwicklung der Wurzel liefert eine explizite Formel \[ c_n = {1 \over n+1} {2\,n \choose n} \] Daraus (wie auch aus der obigen Rekursion) kann man die ersten Werte schnell berechnen: \[ (c_n)_{n \geq 0} = (1,1,2,5,14,42,132,429, \ldots) \] Die Frage, wie schnell diese Folge w"achst, l"asst sich dank der expliziten Formel und der {\sc Stirling}-Formel f"ur $n!$ \[ n! \approx \left( {n \over e} \right)^n \sqrt{2 \pi n} \] leicht beantworten: \[ c_n \approx {1 \over n+1} {4^n \over \sqrt{\pi n}} \] und dies zeigt, da"s das exponentielle Wachstum durch $4^n$ gegeben ist --- es ist also $K_c = 1/4$ --- und da"s der subexponentielle Anteil am Wachstum \[ \tilde{c}_n = {1 \over (n+1) \sqrt{\pi n} } \in \Theta(n^{-3/2}) \] betr"agt. \end{enumerate} \subsection{Zur Bedeutung des Konvergenzradius} Ist $\alpha(z) = \sum_{n \geq 0} a_n \, z^n$ eine Potenzreihe und $K_{\alpha}$ ihr Konvergenzradius, so bedeutet das, da"s auf dem Kreisrand \[ \{ ~z \in {\bf C}~;~|z| = K_{\alpha} ~\} \] in der komplexen Ebene etwas vorkommt, was den Konvergenzradius der Reihe daran hindert, gr"o"ser zu sein: (mindestens) eine {\em Singularit"at} $z_0$ der Funktion $\alpha(z)$. Anders formuliert: der Konvergenzradius $K_{\alpha}$ ist der Radius der gr"o"sten Kreises um den Nullpunkt, der in seinem Innern keine Singularit"at der Funktion enth"alt. Der Begriff {\em Singularit"at} kann hier nicht eingehender er"ortert werden. Dies pr"azise zu behandeln ist eine Aufgabe der komplexen Analysis, der {\em Funktionentheorie}. Hier soll es gen"ugen, dies anhand der vorigen Beispiele zu illustrieren: \begin{enumerate} \item Geometrische Reihe: An der Stelle $z_0 = 1/a$ ist der Ausdruck $1/(1-a\,z)$ nicht definiert; es handelt sich um eine sogenannte {\em Polstelle} der Funktion. Polstellen sind Singularit"aten eines einfachen Typs. Allgemein gilt folgende Aussage: ist $f(z) = p(z)/q(z)$ eine {\em rationale Funktion}, d.h. sind $p(z), q(z)$ Polynome mit (komplexen) Koeffizienten, so sind die Singularit"aten von $f(z)$ genau die Nullstellen des Nennerpolynoms $q(z)$ (vorausgesetzt, da"s die beiden Polynome $p(z)$ und $q(z)$ keinen gemeinsamen Teiler (= keine gemeinsame Nullstelle) haben. Der Konvergenzradius von $f(z)$ ist der kleinste Absolutbetrag einer Nullstelle von $q(z)$. Ist also \[ f(z) = \sum_{n \geq 0} f_n \, z^n = {p(z) \over q(z)} \] eine rationale Funktionen, so kennt man das exponentielle Wachstumsverhalten der Folge $(f_n)_{n \geq 0}$, wenn man die betragsm"a"sig kleinste Nullstelle von $q(z)$ kennt. \item Logarithmische Reihe: An der Stelle $z_0 = 1/a$ ist auch $- \log (1-a\,z)$ nicht definiert. Es handelt sich hier um eine sog. {\em logarithmische Singularit"at}. \item {\sc Catalan}-Zahlen: Hier ist die Situation etwas subtiler: an der Stelle $z_0 = 1/4$ w"are der funktionale Ausdruck $c(z) = (1- \sqrt{1-4z})/(2z)$ durchaus sinnvoll zu definieren. Um zu sehen, da"s hier etwas ``passiert'', muss man sich vergegenw"artigen, da"s $\sqrt{}$ eine {\em mehrdeutige} Funktion ist: $\sqrt{y}$ ist ja definiert als die L"osung(en) der Gleichung $z^2 = y$, und davon gibt es zwei verschiedene, au"ser wenn $y=0$ ist. Eine algebraische Gleichung ( = Polynomgleichung) $n$-ten Grades (in $z$) $p(z,y)=0$ hat (f"ur festes $y$) in der Regel $n$ {\em verschiedene} L"osungen. Werte $y$, wo dies nicht der Fall ist, nennt man {\em algebraische Singularit"aten}. Auch diese kommen als ``Verursacher'' eines Konvergenzradius in Frage, so wie man das bei $c(z)$ sieht, wo $y=1/4$ algebraische Singularit"at ist. \end{enumerate} Bei all diesen Beispielen sieht man, da"s sich die ``Singularit"at kleinsten Absolutbetrages'', die also den Konvergenzradius bestimmt, auf der positiven reellen Achse befindet. Das ist kein Zufall! Es gilt allgemein der Satz: hat eine Potenzreihe nichtnegative reelle Koeffizienten, so befindet sich eine Singularit"at kleinsten Absolutbetrages auf der positiven reellen Achse (falls nicht der Konvergenzradius unendlich ist, d.h. "uberhaupt keine Singularit"aten im endlichen Bereich vorhanden sind). Das ist f"ur die Komplexit"atsanalyse eine gute Nachricht, denn da sind die Koeffizienten von Natur aus nichtnegativ! Um das exponentielle Wachstumsverhalten einer Folge $(a_n)_{n \geq 0}$ von ``Kosten'' zu kennen, mu"s man also nur $\alpha(z) = \sum_{n \geq 0} a_n \, z^n$ auf der positiven reellen Achse untersuchen und dort die kleinste ``verd"achtige'' Stelle ausfindig machen. Ein instruktives Beispiel zu diese Aussage: Bezeichne $m_n$ die Anzahl der un"ar-bin"aren B"aume mit genau $n+1$ Knoten. Das sind also B"aume, deren Verzweigungsgrad bei den inneren Knoten entweder 1 oder 2 betr"agt. Die treten nat"urlicherweise da auf, wo man es mit arithmetische Ausdr"ucken zu tun hat, bei denen sowohl einstellige wie zweistellige Operationssymbole auftreten. Die ersten Werte sind \[ (m_n)_{n \geq 0} = (1,1,2,4,9,21,51, \ldots) \] Im Gegensatz zu der Situation bei den {\sc Catalan}-Zahlen gibt es hier keine einfache Formel f"ur die $m_n$. Das einfachste, was man sagen kann ist \[ m_n = \sum_{k=0}^{\lfloor n/2 \rfloor} c_k {n \choose 2k} \] und wie man daraus etwas "uber das Verhalten f"ur $n \rightarrow \infty$ erfahren soll, ist nicht so klar. Man kann aber (entweder mit Hilfe dieser Summenformel und dem, was man "uber die {\sc Catalan}-Zahlen wei"s, oder aber direkt aus dem Modell der un"ar-bin"aren B"aume) eine Darstellung der zugeh"origen Potenzreihe herleiten: \[ m(z) = \sum_{n \geq 0} m_n \, z^n = {1 - z - \sqrt{1 - 2z - 3z^2} \over 2 z^2} \] Die kritischen Punkt ist dort, wo der Term unter der Wurzel 0 wird. Nun gilt aber \[ 1-2z-3z^2 =(1+z)(1-3z) \] d.h. kritisch sind die Werte $z_0 = -1$ und $z_1 = 1/3$. Dabei ist $z_1 = 1/3$ der betragsm"assig kleinste Wert, als ist der Konvergenzradius von $m(z)$ der Wert $K_m=1/3$ und man wei"s ohne weitere Rechnerei, da"s das exponentielle Verhalten von $(m_n)_n \geq 0$ durch $3^n$ gegeben ist. Durch st"arkere Methoden, die im n"achsten Abschnitt nur angedeutet werden, erh"alt man genauere Auskunft auch "uber den subexponentiellen Anteil: \[ m_n \approx 3^n \, \sqrt{3 \over 4\,\pi\,n^3} \] \subsection{St"arkere Methoden} Die obigen Ausf"uhrungen sollen zeigen, da"s man mit Hilfe des Konvergenzradius einer Potenzreihe oft mit recht elementaren Mitteln zu Aussagen "uber das Wachstumsverhalten einer Folge von reellen Zahlen kommen kann --- zumindest was den exponentiellen Anteil am Wachstum betrifft. Diese erfreuliche Feststellung l"asst aber gleichzeitig zwei (miteinander verwandte) Fragen unbeantwortet: \begin{itemize} \item Wie erf"ahrt man etwas genaueres, quantitatives "uber das Verhalten des ``subexponentiellen'' Anteils? \item Was macht man eigentlich, wenn der Konvergenzradius unendlich ist --- bei Funktionen also, deren Potenzreihenentwicklung in des gesamten komplexen Ebene konvergiert? (Solche Funktionen, zu denen so bekannte Beispiele wie Polynome, Exponentialfunktion, Sinus usw. geh"oren, nennt man auch {\em ganze} Funktionen). \end{itemize} Wiederum kann es hier nur um eine Andeutung gehen. Praktisch alle Methoden zur Beantwortung dieser beiden Fragen (``Sattelpunktmethode'', ``Methode von Heyman/Richman'', ``Transfermethode'', ...) bedienen sich eines ganz zentralen Resultates der Funktionentheorie, der sog. {\em Integralformel von} {\sc Cauchy}: Ist $f(z)$ eine ``analytische'' Funktion, d.h. hat $f(z)$ eine Potenzreihenentwicklung \[ f(z) = \sum_{n \geq 0} f_n \, z^n \] die in einer Umgebung des Nullpunktes konvergiert, so gilt \[ f_n = {1 \over 2 \pi i} \oint {f(z) \over z^{n+1}} \, dz~~~(n \geq 0) \] wobei $\oint$ f"ur ein komplexes Kurvenintegral steht, bei dem sich der Integrationsweg einmal im Gegenuhrzeigersinn um den Nullpunkt herumwindet, dabei aber nat"urlich im Definitionsbereich von $f(z)$ verbleibt. Um den Zusammenhang mit vorher Gesehenem herzustellen, und um zu motivieren, warum es Sinn machen k"onnte, solche Dinge zu betrachten, hier eine ganz simple Anwendung: W"ahlt man als Weg um den Nullpunkt einfach den Kreis mit Radius $r>0$, also \[ \{ z \in {\bf C} ~;~ |z| = r ~\} = \{ r \cdot e^{i\phi}~;~ 0 \leq \phi \leq 2 \pi ~\} \] wobei $r < K_f$ sein soll, so gilt \[ f_n = {1 \over 2 \pi i} \oint {f(z) \over z^{n+1}} \, dz = {1 \over 2 \pi r^n} \int_{0}^{2 \pi} {f(r \cdot e^{i \phi}) \over e^{i n \phi}} \,d\phi ~~~(n \geq 0) \] Bezeichnet nun $M_r(f) := \max_{|z|=r} | f(z) | $ das Maximum von $f(z)$ entlang dieses Integrationswegs, so erh"alt man \[ |f_n| \leq {1 \over 2 \pi r^n} \int_0^{2 \pi} \left| {M_r(f) \over e^{i n \phi} }\right| \, d \phi ={M_r(f) \over r^n} \] und das besagt ja gerade \[ |f_n| \in O(r^{-n}) \] f"ur jedes $r$ mit $0 < r < K_f$. Dies ist also nichts anderes als die eine Seite der Absch"atzung aus dem Wachstumskriterium mittels Konvergenzradius. Speziell der Fall $f(z) = e^z$ liefert wegen $f_n = 1/n!$ \[ {1 \over n!} \leq {e^r \over r^n} \] und dies gilt f"ur alle $r>0$, da ja der Konvergenzradius von $e^z$ unendlich ist. Also \[ {1 \over n!} \leq \min_{r>0} {e^r \over r^n} = {e^n \over n^n} \] und das ist ein Schritt in Richtung auf die Formel von {\sc Stirling}. Um diesem ersten Schritt noch einen zweiten folgen zu lassen: hier ist ein ``Rezept'', wie man in vielen F"allen bei Reihen $f(z) = \sum_{n \geq 0} f_n \, z^n$ mit unendlichem Konvergenzradius ($K_f = \infty$) etwas "uber das Wachstum der Koeffizientenfolge $(f_n)_{n \geq 0}$ erfahren kann: \begin{itemize} \item[-] sei $a(z) := z \cdot f'(z)/f(z)$ und $b(z) := z \cdot a'(z)$ \item[-] berechne $r_n > 0$ mit $a(r_n) = n$ (unter vern"unftigen Bedingungen ist $r_n$ eindeutig bestimmt) \item[-] dann gilt \[ f_n \approx {f(r_n) \over r_n^n \sqrt{2 \pi b(r_n)}} \] \end{itemize} Also kleine Anwendung und Illustration: mit $f(z) = e^z$ ist $a(z) = z$ und $b(z) = z$, $r_n = n ~(n \geq 0)$ und somit \[ {1 \over n!} \approx {e^n \over n^n \sqrt{2 \pi n}} \] und das kommt der Wahrheit der {\sc Stirling}-Formel schon ein gutes St"uck n"aher. \subsection{Literaturhinweise} Wer einmal sehen will, wie die hier nur angedeuteten Methoden funktionieren, wof"ur man sie einsetzt, bis hin zu Systemen der automatischen Komplexit"atsanalyse von Programmen, kann sich in dem folgenden Artikel informieren, der seinerseits reichhaltige Information "uber grundlegende mathematische und weiterf"uhrende Literatur enth"alt: \begin{quote} P. Flajolet, B. Salvy, P. Zimmermann : ``Automatic average case analysis of algorithms'', {\em Theoretical Computer Science}, Band 79 (1991), 37-109. \end{quote} Ein Tutorial zu diesem Thema (ohne Ber"ucksichtigung der neuesten Methoden der automatischen Analyse) enth"alt der Beitrag \begin{quote} P. Flajolet : ``Mathematical methods in the analysis of algorithms and data structures'', in: E. B"orger (Hrsg.), {\em Trends in Theoretical Computer Science}, Computer Science Press, 1988, 225-304. \newline Gruppenbibliothek Informatik: 14GI/mat 7.2-520. \end{quote} Schlie"slich ein enzyklop"adischer Handbuchartikel zum Thema: \begin{quote} J.S. Vitter und P. Flajolet : ``Average case analysis of algorithms and data structures'', Kapitel 9 im {\em Handbook of Theoretical Computer Science}, herausgegeben von J.v. Leeuwen, Elsevier, 1990, Band A, 432-524. \newline Gruppenbibliothek Informatik: 14GI/mat 7-31. \end{quote} \end{document}