Kurs:Algorithmen und Datenstrukturen/Vorlesung/Mastertheorem




MastertheoremBearbeiten

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  .

Fall 1Bearbeiten

Wenn  . Daraus folgt, dass f(n) polynomiell langsamer wächst als   um einen Faktor  . Damit haben wir die Lösung  .

Fall 2Bearbeiten

Wenn  . Daraus folgt, dass f(n) und   vergleichbar schnell wachsen. Damit haben wir die Lösung  .

Fall 3Bearbeiten

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  .

BedeutungBearbeiten

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.

RegularitätsbedingungBearbeiten

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  

 

ÜberblickBearbeiten

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  

IdeeBearbeiten

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.

 

Beispiel 1Bearbeiten

 

 

 

Fall 1:  

 

Beispiel 2Bearbeiten

 

 

 

Fall 2:  

 

Beispiel 3Bearbeiten

 

 

 

Fall 3:  

und   (Regularitätsbedingung)

für  

 

Beispiel 4Bearbeiten

 

 

 

Welcher Fall liegt nun vor? Das Mastertheorem kann an dieser Stelle nicht benutzt werden, da

  • 1. Fall  
  • 2. Fall  
  • 3. Fall  

Nützliche HinweiseBearbeiten

  • Basisumrechnung

 

  • de L'Hospital

 


  • Vergleiche Logarithmus vs. Polynom