Lösen von Rekurrenzgleichungen
Aus ProgrammingWiki
Viele Algorithmen lassen sich rekursiv formulieren. Aus rekursiven Definitionen kann die Aufwandsfunktion $T$ unmittelbar, d.h. offensichtlich und ohne zusätzliche Rechnung abgelesen werden. D.h., es ergibt sich so etwas wie $T(n)=\ldots T(g(n))\ldots$. Wir suchen jedoch einen expliziten Zusammenhang zwischen $T(n)$ und $n$, d.h. ohne Rekursion. Die Problemlösung wird verlagert. Also benötigen wir für die Effizienzanalyse solcher Algorithmen ein allgemeingültiges Verfahren, das diese rekursiven Gleichungen (Rekurrenz- oder Rekursionsgleichungen) löst.
Inhaltsverzeichnis |
Geeignete Kurve bestimmen
Ein typisches Beispiel ist die Fibonacci-Folge: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,\ldots$.
Die Bildungsvorschrift der $n$-ten Fibonacci-Zahl lässt sich sehr leicht angegeben, wenn dies rekursiv geschieht:
$$ \begin{eqnarray} fib(0) & = & 0 \\ fib(1) & = & 1 \\ fib(n) & = & fib(n - 1) + fib(n - 2), n \geqslant 2 \end{eqnarray} $$
Die $n$-te Fibonacci-Zahl ist gleich der Summe der zwei vorhergehenden Fibonacci-Zahlen.
Der Zeitaufwand lässt sich (als Funktion) daraus unmittelbar ablesen und durch eine rekursive Definition ausdrücken:
$$ \begin{eqnarray} T(0) & = & 1 \\ T(1) & = & 1 \\ T(n) & = & T(n - 1) + T(n - 2), n\geqslant 2 \end{eqnarray} $$
Für $T$ benötigen wir einen Ausdruck in $n$ allerdings ohne $T(i)$ auf der rechten Seite. Wir gewinnen diesen Ausdruck dadurch, dass wir die Funktionswerte berechnen und eine Kurve bestimmen, die die Punkte optimal approximiert. Der Verlauf lässt einen exponentiellen Zusammenhang vermuten.
Das Ergebnis ist bekannt, da wir die explizite Formel (Binet, 1843) für die Fibonacci-Zahlen kennen. $$fib(n)=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right)\text{ für } 0\leq n.$$
Hieraus erkennt man $T(n) = \mathcal{O}(a^n)\text{ mit } a>1$, d.h. exponentiellen Aufwand.
Raten und Einsetzen
Eine solche Lösungsmethode ist das Intelligent guesswork - das geschickte Raten. Hierfür stellt man eine Wertetabelle für $T(n)$ auf und versucht daraus eine explizite Bildungsvorschrift zu erkennen.
Beispiel
$$ \begin{align} T(1) & = 1 \\ T(n) & = 3 \cdot T \left(\frac{n}{2} \right) + n \end{align} $$
$n$ sei hierbei eine Zweierpotenz, d.h. $n = 2^k$ mit $k \in \mathbb{N}$.
Gibt man zusätzlich zu den Funktionswerten die Summendarstellungen an, ergibt sich folgende Wertetabelle:
| $n$ | $T(n)$ |
|---|---|
| $1$ | $1$ |
| $2$ | $5=3 \cdot 1 + 2$ |
| $4$ | $19=3^2 \cdot 1 + 3 \cdot 2 + 2^2$ |
| $8$ | $65=3^3 \cdot 1 + 3^2 \cdot 2 + 3 \cdot 2^2 + 2^3$ |
| $16$ | $211=3^4 \cdot 1 + 3^3 \cdot 2 + 3^2 \cdot 2^2 + 3 \cdot 2^3 + 2^4$ |
| $32$ | $665=3^5 \cdot 1 + 3^4 \cdot 2 + 3^3 \cdot 2^2 + 3^2 \cdot 2^3 + 3 \cdot 2^4 + 2^5$ |
Mit Hilfe dieser Summendarstellung lässt sich ein gewisses Muster erkennen, dadurch kann die Lösung "erraten" werden.
$$ \begin{align*} T(2^k) & = 3^k \cdot 2^0 + 3^{k-1} \cdot 2^1 + ... + 3^1 \cdot 2^{k-1} + 3^0 \cdot 2^k \\ & = \sum_{i=0}^{k}(3^{k-i} \cdot 2^i) \\ & = 3^k \sum_{i=0}^k \left(\frac{2}{3} \right)^i \\ & = 3^k \frac{1- \left(\frac{2}{3}\right)^{k+1}}{1-\frac{2}{3}} \\ T(2^k) & = 3^{k+1} - 2^{k+1} \end{align*} $$
Um eine Funktion $n \mapsto T(n)$ zu erhalten, muss $k$ durch $\log_2 n$ ersetzt werden.
$$ \begin{align*} T(n) & = 3^{\log_2 n + 1} - 2^{\log_2 n + 1} \\ & = 3^{\log_2 n} \cdot 3^1 - 2^{\log_2 n} \cdot 2^1 \\ & = 3 \cdot 3^{\log_2 n} - 2 \cdot 2^{\log_2 n} \\ T(n) & = 3 \cdot n^{\log_2 3} - 2 \cdot n \end{align*} $$
Um die asymptotische Aufwandsordnung anzugeben, können der Summand $-2n$ und der Faktor $3$ vernachlässigt werden. Dies ergibt $\mathcal{O}(n^{\log_2 3})$.
Iterationsmethode
Bei der Iterationsmethode wird eine rekursive Vorschrift solange angewandt, bis man zu einem rekursionsfreien Ausdruck gelangt. Dies geschieht durch wiederholtes Einsetzen der rekursiven Funktionsaufrufe. Diese Expansion durch Selbstanwendung wird Telescoping genannt.
Hat man eine rekursive Funktion $n\mapsto T(n)$ und setzt man für $n$ einen konkreten Wert ein, so kann problemlos Telescoping angewandt werden, da in endlich vielen Schritten die Elementarfälle erreicht werden und ein rekursionsfreier Ausdruck entsteht. Möchte man aber eine rekursive Funktion $n\mapsto T(n)$ für ein allgemeines $n$ mit Hilfe der Iterationsmethode lösen, so ist ein mathematischer Zwischenschritt nötig.
Beispiel
$$ \begin{align*} T(1) & = 1 \\ T(n) & = 2 \cdot T \left(\frac{n}{4} \right) + n \end{align*} $$
Die Gleichung wird nun schrittweise expandiert:
$$ \begin{align*} T(n) & = 2 \cdot T \left(\frac{n}{4} \right) + n \\ & = 2 \cdot \left(2 \cdot T \left(\frac{n}{16} \right) + \frac{n}{4} \right) + n \\ & = 4 \cdot T \left(\frac{n}{16} \right) + \frac{3}{2}n \\ & = 4 \cdot \left(2 \cdot T \left(\frac{n}{64} \right) + \frac{n}{16} \right) + \frac{3}{2}n \\ & = 8 \cdot T \left(\frac{n}{64} \right) + \frac{7}{4}n \\ & = 8 \cdot \left(2 \cdot T \left(\frac{n}{256} \right) + \frac{n}{64} \right) + \frac{7}{4}n \\ & = 16 \cdot T \left(\frac{n}{256} \right) + \frac{15}{8}n \\ \end{align*} $$
Es wird ein gewisses Muster für den gesuchten, $T(n)$ definierenden Ausdruck ersichtlich, welches sich mit einer Variable $i$ mit $i\geqslant 1$ ausdrücken lässt.
$$ \begin{align*} T(n) & = 2^i \cdot T \left(\frac{n}{4^i} \right) + \frac{2^i - 1}{2^{i-1}} \cdot n \\ \end{align*} $$
Nun muss $i$ so gewählt werden, dass aus $T\left(\frac{n}{4^i}\right)$ ein rekursionsfreier Ausdruck ensteht, d.h. der Elementarfall erreicht ist. Dies geschieht mit $i = \log_4 n$ bei $T(1)$:
$$ \begin{align*} T\left(\frac{n}{4^i}\right) & = T(1) \\ \frac{n}{4^i} & = 1 \\ n & = 4^i \\ i & = \log_4 n \end{align*} $$
Wir setzen $\log_4 n$ für $i$ in dem oben für $T(n)$ angegebenen "Musterausdruck" ein:
$$ \begin{align*} T(n) & = 2^{\log_4 n} \cdot T \left(\frac{n}{4^{\log_4 n}} \right) + \frac{2^{\log_4 n} - 1}{2^{\log_4 n - 1}} \cdot n \\ & = n^{\log_4 2} \cdot T(1) + \frac{n^{\log_4 2} - 1}{\frac{2^{\log_4 n}}{2}} \cdot n \\ & = n^{\log_4 2} \cdot T(1) + \frac{n^{\log_4 2} - 1}{\frac{n^{\log_4 2}}{2}} \cdot n \\ & = n^{\frac{1}{2}} \cdot T(1) + \frac{n^{\frac{1}{2}} - 1}{\frac{n^{\frac{1}{2}}}{2}} \cdot n \\ & = n^{\frac{1}{2}} + \frac{2n^{\frac{1}{2}} - 2}{n^{\frac{1}{2}}} \cdot n \\ & = n^{\frac{1}{2}} + \frac{2n^{\frac{3}{2}} - 2n}{n^{\frac{1}{2}}} \\ & = n^{\frac{1}{2}} + \frac{2n^{\frac{3}{2}} - 2n}{n^{\frac{1}{2}}} \\ & = n^{\frac{1}{2}} + 2n - 2n^\frac{1}{2} \\ T(n) & = 2n - n^\frac{1}{2} \end{align*} $$
Interessiert man sich nur für die asymptotische Aufwandsordnung, so liegt mit $T(n) \in \mathcal{O}(n)$ ein linearer Zusammenhang vor.
Übungsaufgabe
Lösen Sie folgende Rekursionsgleichung mit der Iterationsmethode.
$$ \begin{align*} \\ T(1) & = 1\\ T(n) & = n + 3 \cdot T \left(\frac{n}{4} \right), \text{für } n = 4^k , k \in \mathbb{N} \end{align*} $$
Lösung:
$$ \begin{align*} \\ T(n) &= 3 \cdot T \left(\frac{n}{4} \right) + n \\ T(n) &= 3 \cdot \left( 3 \cdot T \left(\frac{n}{16}\right) + \frac{n}{4} \right) + n \\ T(n) &= 9 \cdot T \left(\frac{n}{16} \right) + \frac{3}{4} n + n \\ T(n) &= 9 \cdot \left( 3 \cdot T \left(\frac{n}{64} \right) + \frac{n}{16} \right) + \frac{3}{4} n + n \\ T(n) &= 27 \cdot T \left(\frac{n}{64} \right) + \frac{9}{16} n + \frac{3}{4} n + n \\ T(n) &= 27 \cdot \left( 3 \cdot T \left(\frac{n}{256} \right) + \frac{n}{64} \right) + \frac{9}{16} n + \frac{3}{4} n + n \\ T(n) &= 81 \cdot T \left(\frac{n}{256} \right) + \frac{27}{64} n + \frac{9}{16} n + \frac{3}{4} n + n \\ T(n) &= 3^i \cdot T \left(\frac{n}{4^i} \right) + \sum_{j=0}^\infty \left( \left( \frac{3}{4} \right)^j \right) \cdot n \\ T(n) &= 3^i \cdot T \left(\frac{n}{4^i} \right) + \frac{1}{1 - \frac{3}{4}} \cdot n \\ T(n) &= 3^i \cdot T \left(\frac{n}{4^i} \right) + 4 \cdot n \\ \\ T \left(\frac{n}{4^i} \right) & = T(1) \\ \frac{n}{4^i} &= 1 \\ n &= 4^i \\ i &= \log_4 n \\ \\ T(n) &= 3^{\log_4 n} \cdot T(1) + 4 \cdot n \\ T(n) &= n^{\log_4 3} + 4 \cdot n \\ T(n) &\in \mathcal{O}(n) \end{align*} $$
Meistermethode (Master method)
Die Meistermethode bietet eine Möglichkeit, die asymptotische Aufwandsordnung für Divide and Conquer-Algorithmen zu bestimmen. Für den Zeitaufwand von Divide-and-Conquer-Algorithmen gilt $$T(n) = a \cdot T \left(\frac{n}{b} \right) + f(n).$$
Beispiel
Für $T(n) = 2 \cdot T \left(\frac{n}{4} \right) + n$ ergeben sich $a$, $b$ und $f(n)$ durch pattern matching: $$ \begin{eqnarray} a & = 2 \\ b & = 4 \\ f(n) & = n \end{eqnarray} $$
Nun muss man versuchen, den Ausdruck in einen der folgenden drei Fälle einzuordnen. Wenn dies gelingt, ergibt sich die Lösung unmittelbar aus der Variablenbindung. Wenn nicht, ist die Mastermethode zur Lösung der vorliegenden Rekurrenzgleichung nicht anwendbar.
Definition 2.1 (Master Theorem)
Fall 1
Wenn $f(n) \in \mathcal{O} \left(n^{\log_b a - \epsilon} \right)$ mit $\epsilon > 0$, dann $T(n) \in \Theta \left(n^{\log_b a} \right)$.
Der größte Aufwand besteht hier im Teilen in Subprobleme, die Rekursion ist somit wurzellastig (root-heavy).
Fall 2
Wenn $f(n) \in \Theta \left(n^{\log_b a} \right)$, dann $T(n) \in \Theta \left(n^{\log_b a}\log n \right)$.
Der Aufwand zum Rekombinieren der gelösten Subprobleme ist gleichwertig mit dem des Teilens.
Fall 3
Wenn $f(n) \in \Omega \left(n^{\log_b a + \epsilon} \right)$ mit $\epsilon > 0$, dann $T(n) \in \Theta(f(n))$.
In diesem Fall liegt der größte Aufwand im Rekombinieren, die Rekursion ist also blattlastig (leaf-heavy).
Beispiel
Für das oben angegebene Beispiel gilt Fall 3 des Master Theorems.
Setzt man $a=2, b=4$ und $f(n)=n$ in $f(n) \in \Omega \left(n^{\log_b a + \epsilon} \right)$ ein, so ergibt sich $n \in \Omega \left(n^{\log_4 2 + \epsilon} \right) = \Omega \left(n^{\frac{1}{2} + \epsilon} \right) = \Omega(n^1)$. Hieraus folgt $\epsilon=\frac{1}{2} > 0$.
Folglich gilt für die Aufwandsordnung $T(n)\in\Theta(n)$. Das Verfahren arbeitet mit linearem Aufwand.
Übungsaufgabe
Der (hier nicht näher betrachtete) Algorithmus Mergesort, welcher zum Sortieren von Listen verwendet wird, arbeitet mit folgendem Zeitaufwand:
$$ \begin{align*} T(0) &= 1 \\ T(1) &= 1 \\ T(n) &= 2\cdot T\left(\frac{n}{2} \right) + \mathcal{O}(n) \end{align*} $$
Ermitteln Sie eine zugehörige Aufwandsfunktion $T$ in expliziter Form mit Hilfe der Meistermethode.
Lösung
$$ \begin{align*} \\ a &= 2 \\ b &= 2 \\ f(n) &= \mathcal{O}(n) \\ \\ \text{Da } f(n) & \in \Theta \left(n^{\log_2 2} \right) \text{ , gilt Fall 2:} \\ \\ T(n) & \in \mathcal{O} \left(n^{\log_2 2} \log n \right) = \mathcal{O}(n \log n) \end{align*} $$
Übungsaufgabe
Nehmen wir an, ein Algorithmus löst ein Problem der Größe $n$, indem er es rekursiv in höchstens $A \cdot \sqrt{n}$ Zeit auf zwei gleichartige Probleme der Größen von jeweils $\frac{n}{4}$ zurückführt. Geben Sie die asymptotische Laufzeit $T(n)$ an.
Lösung
$$ \begin{align*} \\ T(n) &= 2 \cdot T \left( \frac{n}{4} \right) + A \cdot \sqrt{n} \\ \\ \text{Meistermethode:} \\ a &= 2 \\ b &= 4 \\ f(n) &= A \cdot \sqrt{n} \\ \text{Da } f(n) & \in \Theta \left(n^{\log_4 2} \right) = \Theta \left(n^{\frac{1}{2}} \right) \text{ , gilt Fall 2:} \\ \\ T(n) & \in \Theta \left( \sqrt{n} \log n \right) \text{ und wegen } \log n < \sqrt{n} \\ T(n) & \in \Theta(n) \end{align*} $$
