Master-Theorem
Der Hauptsatz der Laufzeitfunktionen oder oft englisch Master-Theorem, das ein Spezialfall des Akra-Bazzi-Theorems ist, bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt. Jedoch kann mit dem Master-Theorem nicht jede rekursiv definierte Funktion gelöst werden. Lässt sich keiner der drei möglichen Fälle des Master-Theorems auf die Funktion T anwenden, so muss man die Komplexitätsklasse der Funktion anderweitig berechnen.
Inhaltsverzeichnis
Allgemeine Form
Die allgemeine Form für die Anwendung des Master-Theorems sieht wie folgt aus:
<math>T(n) = a \sdot T(\textstyle \frac{n}{b}) + f(n)</math>
Hierbei steht <math>T(n)</math> für die zu untersuchende Laufzeitfunktion, während <math>a</math> und <math>b</math> Konstanten sind. Ferner bezeichnet <math>f(n)</math> eine von <math>T(n)</math> unabhängige und nicht negative Funktion. Damit das Master-Theorem angewendet werden kann, muss für die beiden Konstanten die Bedingung <math>a \ge 1</math> und <math>b > 1</math> erfüllt sein.
Interpretation der Rekurrenz <math>T(n)</math>:
- <math>a</math> = Anzahl der Unterprobleme in der Rekursion
- <math>1/b</math> = Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird
- <math>f(n)</math> = Kosten (Aufwand, Nebenkosten), die durch die Division des Problems und die Kombination der Teillösungen entstehen
Das Master-Theorem unterscheidet drei Fälle, wobei sich höchstens ein Fall auf die gegebene Rekursion anwenden lässt. Passt keiner der Fälle, so lässt sich das Master-Theorem nicht anwenden und man muss sich anderer Methoden bedienen.
Erster Fall | Zweiter Fall | Dritter Fall | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
|
<math>f(n) \in \mathcal{O}\left( n^{\log_b a - \varepsilon} \right)</math> für ein <math>\varepsilon>0</math> |
<math>f(n) \in \Theta\left( n^{\log_b a} \right)</math> |
| |||||||||
Dann folgt: | <math>T(n) \in \Theta\left( n^{\log_b a} \right)</math> | <math>T(n) \in \Theta\left( n^{\log_b a} \log(n)\right)</math> | <math>T(n) \in \Theta(f(n))</math> | |||||||||
Beispiel | <math>T(n) = 8 T(\textstyle \frac{n}{2}) + 1000n^2</math> | <math>T(n) = 2 T(\textstyle \frac{n}{2}) + 10n</math> | <math>T(n) = 2 T(\textstyle \frac{n}{2}) + n^2</math> | |||||||||
Aus der Formel ist folgendes abzulesen: |
|
|
| |||||||||
1. Bedingung: | <math>f(n) \in \mathcal{O}\left( n^{\log_b a - \varepsilon} \right)</math> für ein <math>\varepsilon > 0</math> |
<math>f(n) \in \Theta\left( n^{\log_b a} \right)</math> | <math>f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)</math> für ein <math>\varepsilon > 0</math> | |||||||||
Werte einsetzen: | <math>1000n^2 \in \mathcal{O}\left( n^{3 - \varepsilon} \right)</math> | <math>10n \in \Theta\left( n^{1} \right)</math> | <math>n^2 \in \Omega\left( n^{1 + \varepsilon} \right)</math> | |||||||||
Wähle <math> \varepsilon > 0</math>: | <math>1000n^2 \in \mathcal{O}\left( n^{2}\right)</math> mit <math> \varepsilon = 1</math> ✔ | <math>10n \in \Theta\left( n \right)</math> ✔ | <math>n^2 \in \Omega\left( n^2 \right)</math> mit <math> \varepsilon=1</math> ✔ | |||||||||
2. Bedingung: (nur im 3. Fall) |
| |||||||||||
Damit gilt für die Laufzeitfunktion: | <math>T(n) \in \Theta( n^{3} )</math> | <math>T(n) \in \Theta( n \log(n))</math> | <math>T(n) \in \Theta(n^2)</math> |
( ✔ = Wahre Aussage )
Verallgemeinerung des zweiten Falls
Nicht alle Rekurrenzgleichungen lassen sich mithilfe einer der drei Fällen des Mastertheorems lösen. So ist zum Beispiel die folgende Rekurrenzgleichung nicht direkt mit dem Mastertheorem lösbar.
<math>T(n) = 8 T( \textstyle \frac{n}{2}) + n^3\ln(n)</math>.
Auf den ersten Blick scheint es, dass der 3. Fall anzuwenden ist:
- <math>a=8,</math> <math>b=2</math>, <math>f(n)=n^3\ln(n)</math>
- Für den 3. Fall ist zu zeigen: <math>f(n) \in \Omega\left( n^{\log_b a + \varepsilon} \right)</math>
- Definition vom Ω-Kalkül:<math>f(n) \in \Omega(g(n)) : 0 < \liminf_{n \to \infty} \left|\textstyle \frac{f(n)}{g(n)}\right| \le \infty</math>
- Angewandt auf <math>n^3\ln(n) \in \Omega\left( n^{\log_2 8 + \varepsilon} \right)</math>:
- <math>\exists \varepsilon > 0 : 0 < \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = \liminf_{n \to \infty} \left| \frac{n^3\ln(n)}{n^{\log_2 8 + \varepsilon}}\right| = \liminf_{n \to \infty} \left| \frac{\ln(n)}{n^{\varepsilon}}\right| = 0 \Rightarrow</math> Widerspruch!
- Es existiert kein <math>\varepsilon> 0</math>, so dass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!
Es gilt: <math>T(n) = \Theta\left( n^{\log_b a}\ln^{k+1}n \right)</math>, falls <math>f(n) \in \Theta\left( n^{\log_b a}\ln^{k}n \right)</math>
Genau betrachtet stellt diese Formel eine Verallgemeinerung des zweiten Falls dar.
Lösung nach obiger Formel:
- <math>f(n) = n^3\ln(n) \in \Theta\left( n^{\log_b a}\ln^{k}n \right) = \Theta\left( n^{\log_2 8}\ln^{1}n \right) = \Theta\left(n^{3}\ln(n) \right)</math> ✔
- Da <math>f(n)</math> die hinreichende Bedingung erfüllt, gilt nun: <math>T(n) = \Theta\left( n^{3}\ln^{2}n \right)</math>
- Siehe zu demselben Beispiel auch die Aufwandsabschätzung im Ο-Kalkül mit Hilfe der Substitutionsmethode.
Bemerkungen
- Angenommen, es ist folgende Rekurrenz gegeben, bei der <math>n/b</math> durch die Floor- oder Ceiling-Funktion angegeben werden:
- z. B.: <math>T(n) = a T( \lfloor \tfrac{n}{b} \rfloor ) + f(n)</math>
- In diesem Fall kann man <math>\lfloor \tfrac{n}{b} \rfloor</math> oder auch <math>\lceil \tfrac{n}{b} \rceil</math> mit Hilfe der Form <math>\tfrac{n}{b}</math> abschätzen.
- Ob man nun <math> T(n) \in \Theta (\ln(n))</math> (Logarithmus naturalis) schreibt, oder <math>T(n) \in \Theta (\lg(n))</math> (dekadischer Logarithmus) ist egal, da nach den Logarithmengesetzen gilt:
- <math>\ln(n) = \log_e(n)= \textstyle \frac{\log_{10}(n)}{\log_{10}(e)} = c\sdot \log_{10}{n} \in \Theta( \log_{10}{n}) = \Theta( \lg{n})</math>
Allgemeinere Form
In allgemeinerer Form gilt auch:
Definition
Sei <math>T: \mathbb{N} \to \mathbb{N}</math> die zu untersuchende Abbildung der Form
- <math>T(n) = \sum_{i=1}^{m} T\left(\alpha_i n\right) + f(n)</math>,
wobei <math>\alpha_i \in \mathbb{R}: 0 < \alpha_i < 1</math>, <math>m \in \mathbb{N}: m \ge 1</math> und <math>f(n) \in \Theta(n^k)</math> mit <math>k \in \mathbb{N}: k \ge 0</math>.
<math>T</math> wird hierfür implizit durch <math>T(x) := T(\lfloor x \rfloor)</math> oder <math>T(\lceil x \rceil)</math> für <math>x \in \mathbb{R^+}</math> auf die reellen Zahlen fortgesetzt.
Dann gilt:
- <math>T(n) \in
\begin{cases} \Theta(n^k) & \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) < 1 \\ \Theta(n^k \log n) & \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) = 1 \\ \Theta(n^c) \mbox{ mit } \sum_{i=1}^{m}(\alpha_i^c) = 1 & \mbox{falls } \sum_{i=1}^{m}(\alpha_i^k) > 1 \end{cases}</math>
Literatur
- Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – eine Einführung. Oldenbourg, München, Wien 2004 (Originaltitel: Introduction to algorithms, übersetzt von Karen Lippert, Micaela Krieger-Hauwede), ISBN 3-486-27515-1.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7.