Lösen von Rekurrenzgleichungen
Inhaltsverzeichnis |
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 (Rekurrenzgleichungen) löst.
Regressionsgerade 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) \mid 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) & = & 0 \\ 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 - wie oben ausgeführt - eine zugehörige Regressionsgerade bestimmen.
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}^{k+1} \right)}{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.
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.