- Master-Theorem
-
Der Begriff 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:
Hierbei steht T(n) für die zu untersuchende Laufzeitfunktion, während a und b Konstanten sind. Ferner bezeichnet f(n) eine von T(n) unabhängige und nicht negative Funktion. Damit das Master-Theorem angewendet werden kann, muss für die beiden Konstanten die Bedingung a ≥ 1 und b > 1 erfüllt sein.
Interpretation der Rekurrenz T(n):
- a = Anzahl der Unterprobleme in der Rekursion
- 1 / b = Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird
- f(n) = Kosten (Aufwand), die durch die Division des Problems und der Kombination der Teillösungen entstehen
Weiterhin benötigt man für die Benutzung des Master-Theorems noch den Logarithmus von a zur Basis b, log ba.
Das Master-Theorem unterscheidet sich in 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 Allgemein Falls gilt:
für ein ε > 0für ein ε > 0
und ebenfalls für ein c mit 0 < c < 1 und alle hinreichend großen n gilt: Dann folgt: Beispiel Aus der Formel ist folgendes abzulesen: a = 8, b = 2 f(n) = 1000n2 log ba = log 28 = 3 a = 2, b = 2 f(n) = 10n log ba = log 22 = 1 a = 2, b = 2 f(n) = n2 log ba = log 22 = 1 1. Bedingung:
für ein0" border="0">
für ein
0" border="0">
Werte einsetzen: Wähle 0" border="0">:
mit
✔
✔
mit
✔
2. Bedingung: (nur im 3. Fall) Setze auch hier obige Werte ein: Wähle c = ½: ✔
Damit gilt für die Laufzeitfunktion: ( ✔ = 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.
.
Auf den ersten Blick scheint es, dass der 3. Fall anzuwenden ist:
- a = 8, b = 2, f(n) = n3ln(n)
- Für den 3. Fall ist zu zeigen:
- Definition vom Ω-Kalkül:
- Angewandt auf
:
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" border="0"> Widerspruch!
- Es existiert kein
0" border="0">, sodass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!
Es gilt:
, falls
Genau betrachtet stellt diese Formel eine Verallgemeinerung des zweiten Falls dar.
Lösung nach obiger Formel:
✔
- Da f(n) die notwendige Bedingung erfüllt, gilt nun:
- Siehe zu demselben Beispiel auch die Aufwandsabschätzung im Ο-Kalkül mit Hilfe der Substitutionsmethode.
Bemerkungen
- Angenommen, es ist folgende Rekurrenz gegeben, bei der n / b durch die Floor- oder Ceiling-Funktion angegeben werden:
- z. B.:
- In diesem Fall kann man
oder auch
mit Hilfe der Form
abschätzen.
- Ob man nun
(Logarithmus naturalis) schreibt, oder
(dekadischer Logarithmus) ist egal, da nach den Logarithmengesetzen gilt:
Allgemeinere Form
In allgemeinerer Form gilt auch:
Definition
Sei
die zu untersuchende Abbildung der Form
,
wobei
,
und
mit
.
T wird hierfür implizit durch
oder
für
auf die reellen Zahlen fortgesetzt.
Dann gilt:
1 \end{cases}" border="0">
Literatur
- Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – eine Einführung. Oldenbourg, München, Wien 2004, 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.
Wikimedia Foundation.