Kurs:Algorithmen und Datenstrukturen/Vorlesung/Mastertheorem

Aus Wikiversity
Zur Navigation springen Zur Suche springen




Mastertheorem[Bearbeiten]

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 1[Bearbeiten]

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

Fall 2[Bearbeiten]

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

Fall 3[Bearbeiten]

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 .

Bedeutung[Bearbeiten]

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ätsbedingung[Bearbeiten]

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

Überblick[Bearbeiten]

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

Idee[Bearbeiten]

Wir haben folgenden Rekursionsbaum: Rekursionsbaum_Mastertheorem

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 1[Bearbeiten]

Fall 1:

Beispiel 2[Bearbeiten]

Fall 2:

Beispiel 3[Bearbeiten]

Fall 3:

und (Regularitätsbedingung)

für

Beispiel 4[Bearbeiten]

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

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

Nützliche Hinweise[Bearbeiten]

  • Basisumrechnung

  • de L'Hospital


  • Vergleiche Logarithmus vs. Polynom



Vorheriges Thema.jpg Discussion Nächstes Thema.jpg