Auf dieser Seite wird das Master Theorem behandelt.
Die Mastermethode ist ein „Kochrezept“ zur Lösung von
Rekursionsgleichungen der Form:
mit den Konstanten , f(n) ist eine asymptotische, positive Funktion, d.h.
- a steht dabei für die Anzahl der Unterprobleme.
- n/b ist die Größe eines Unterproblems
- T(n/b) ist der Aufwand zum Lösen eines Unterproblems (der Größe n/b)
- f(n) ist der Aufwand für das Zerlegen und Kombinieren in bzw. von Unterproblemen
Bei der Mastermethode handelt es sich um ein schnelles Lösungsverfahren zur Bestimmung der
Laufzeitklasse einer gegebenen rekursiv definierten
Funktion. Dabei gibt es 3 gängige Fälle:
- Fall 1: Obere Abschätzung
- Fall 2: Exakte Abschätzung
- Fall 3: Untere Abschätzung
Lässt sich keiner dieser 3 Fälle anwenden, so muss die Komplexität anderweitig bestimmt werden und
wir müssen Voraussetzungen für die Anwendung des
Mastertheorems überprüfen.
Dafür vergleicht man mit . Wir verstehen n/b als . Im Folgenden verwenden wir die verkürzte Notation .
Wenn . Daraus folgt, dass f(n) polynomiell langsamer wächst als um einen Faktor . Damit haben wir die Lösung .
Wenn . Daraus folgt, dass f(n) und vergleichbar schnell wachsen. Damit haben wir die Lösung .
Wenn und die Regularitätsbedingung für eine Konstante und genügend große n erfüllt. Daraus folgt, dass f(n) polynomiell schneller wächst als um einen Faktor und f(n) erfüllt die sogenannte Regularitätsbedingung. Damit haben wir die Lösung .
In jedem Fall vergleichen wir f(n) mit . Intuitiv kann man sagen, dass die Lösung durch die größere Funktion bestimmt wird.
Im zweiten Fall wachsen sie ungefähr gleich schnell. Im ersten und dritten Fall muss f(n) nicht nur kleiner oder größer als sein, sondern auch polynomiell kleiner oder größer um einen Faktor .
Der dritte Fall kann nur angewandt werden, wenn die
Regularitätsbedingung erfüllt ist.
Doch wozu wird die Regularitätsbedingung benötigt? Zur Erinnerung, im dritten Fall dominiert f(n) das Wachstum von T(n). Wir müssen an dieser Stelle sicherstellen, dass auch bei rekursivem Anwenden, also wenn die Argumente kleiner werden, T(n) von f(n) dominiert wird. Veranschaulicht heißt das:
für
Das Wachstum muss durch f(n) dominiert werden und darf f(n) nicht dominieren.
Die Regularitätsbedingung gilt wenn sie für f(n) und g(n) gilt auch für und auch für
Nachweis für
Voraussetzung ist, dass die Regularitätsbedingung für f(n) und g(n) gilt, d.h.:
Für gilt:
man wählt
und
Nachweis für
Voraussetzung ist, dass die Regularitätsbedingung für f(n) und g(n) gilt, d.h.:
Für gilt:
man wählt
und
Ist T(n) eine rekursiv definierte Funktion der Form
Dann gilt:
- 1. Fall: Wenn
- 2. Fall: Wenn
- 3. Fall: Wenn und und genügend große n dann
Wir haben folgenden Rekursionsbaum:
Auf der ersten Ebene ist der Aufwand f(n), auf der zweiten Ebene und auf der dritten Ebene . Die Höhe des Baumes beträgt . Die Anzahl der Blätter berechnet sich durch und beträgt somit .
Fall 1:
Das Gewicht wächst geometrisch von der Wurzel zu den Blättern. Die Blätter erhalten einen konstanten Anteil des Gesamtgewichts.
Fall 2:
k ist 0 und das Gewicht ist ungefähr das Gleiche
auf jedem der Ebenen.
Fall 3:
Das Gewicht reduziert sich geometrisch von der Wurzel zu den Blättern. Die Wurzel erhält einen konstanten Anteil am Gesamtgewicht.
Fall 1:
Fall 2:
Fall 3:
und (Regularitätsbedingung)
für
Welcher Fall liegt nun vor? Das Mastertheorem kann an dieser Stelle nicht benutzt werden, da
- 1. Fall
- 2. Fall
- 3. Fall
- Vergleiche Logarithmus vs. Polynom