\documentstyle[12pt,A4,german]{article}
\begin{document}
\Large
\begin{center}
{\bf L\"osungstypen f\"ur die {\em divide-and-conquer}-Rekursion
$t(n) = a \cdot t(n/b) + f(n)$}
\end{center}
\begin{itemize}
\item
Literatur: siehe z.B. die Abschnitte 4.3/4.4 im Buch  
von {\sc Cormen/Leiserson/Rivest} \\
(Stichwort:  ``Master Method'')
\item
Die Rekursion:
\begin{equation}
t(n) = a \cdot t(n/b) + f(n)~~~,~~~
t(1) = f(1) > 0
\end{equation}
mit $b$ ganz und $\geq 2$, $a > 0$ und $f(n) \geq 0$
\item
Bedeutung:
\begin{itemize}
\item
$t(n)$ beschreibt die Kosten f\"ur die Ausf\"uhrung eines Algorithmus
bei Problemgr"o"se $n$.
\item
Zerlegung von Probleminstanzen der Gr\"osse $n$ in $a$
Teilprobleme gleichen Typs der Gr\"osse $n/b$
\item
$f(n)$: {\em overhead}, der bei Problemzerlegung und
Ergebnissynthese f\"ur Probleme der Gr\"osse $n$ anf\"allt
\end{itemize}
\item
Ziel: Beurteilung des Wachstumsverhalten der L"osung $t(n)$ in
Abh"angigkeit von $a,b$ und der {\em overhead}-Funktion $f(n)$
zu erhalten.
\item
Schwierigkeit: $f(n)$ nur in Form einer $\Theta$-Aussage bekannt.
Dann kann auch nur $\Theta$-Aussage f\"ur $t(n)$ gewonnen werden.
\item
Vereinfachung: betrachte $t(n)$ nur f\"ur Argumente $n = b^m$:
\[
t_m := t(b^m) ~~,~~
f_m := f(b^m)~~,~~m=0,1,2,3,\ldots
\]
\item
Ansatz in Potenzreihen:
\[
\tau(z) := \sum_{m \geq 0} t_m \, z^m ~~,~~
\phi(z) := \sum_{m\geq 0} f_m \, z^m
\]
\item
\"Aquivalente Aussage zur Rekursion (1):
\[
\tau(z) = {1 \over 1-az} \cdot \phi(z)
\]
\item
Fallunterscheidung f\"ur die L\"osungstypen:\\
sei $K_\phi$ der Konvergenzradius von $\phi(z)$,
$K_\tau$ der Konvergenzradius von $\tau(z)$, so sind
drei F\"alle zu unterscheiden
\begin{itemize}
\item
\framebox{$K_\phi > 1/a$} : dann gilt 
$K_{\tau} = \min(K_{\phi},1/a) = 1/a$ und es ist
\[
t(n) = t(b^m) = t_m \in \Theta(a^m) = \Theta(n^{\log_b a})
\]
Interpretation:
Anteil der overhead-Kosten ist im Vergleich zur 
Behandlung der Elementarf\"alle
f\"ur grosse Probleminstanzen zu vernachl\"assigen.
\item
\framebox{$K_\phi = 1/a$} : in diesem ``kritischen Fall'' gilt ebenfalls
$K_{\tau} = \min(K_{\phi},1/a) = 1/a$.\\
Falls $f(n) = c \cdot n^k \cdot(\log_b n)^q$, so sind drei
F\"alle zu unterscheiden:
\begin{itemize}
\item
Fall $q < -1$ :
\[
t(n) =t(b^m) \in \Theta(a^m) = \Theta(n^{\log_b a})
\]
\item
Fall $q=-1$ :

\[
t(n) \in \Theta(a^m \, \log m) = \Theta
\left(
n^{\log_b a} \log \log_b n\right)
\]
\item
Fall $q > -1$ :
\[
t(n) \in \Theta(a^m \, m^{q+1}) = 
\Theta \left( n^{\log_b a} \left(\log_b n \right)^{1+q} \right)
\]
\end{itemize}
Interpretation: hier tragen die overhead-Kosten wesentlich, aber nicht
\"uberwiegend zu den Gesamtkosten bei.
\item
\framebox{$K_\phi< 1/a$}: falls $f(n) \in \Theta(n^k)$ mit $a < b^k$ so gilt
\[
t(n) \in \Theta(n^k)
\]
Interpretation: die Gesamtkosten gehen fast ausschliesslich zu Lasten
des overheads.
\end{itemize}
\item
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*}
\end{itemize}

\end{document}