Master-Theorem

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Allgemeine Form[Bearbeiten | Quelltext bearbeiten]

Die allgemeine Form für die Anwendung des Master-Theorems sieht wie folgt aus:

Hierbei steht für die zu untersuchende Laufzeitfunktion, während und Konstanten sind. Ferner bezeichnet eine von unabhängige und nicht negative Funktion. Damit das Master-Theorem angewendet werden kann, muss für die beiden Konstanten die Bedingung und erfüllt sein.

Interpretation der Rekurrenz :

  = Anzahl der Unterprobleme in der Rekursion
= Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird
= 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
Allgemein
Falls gilt:
 
für ein 
 für ein 
und ebenfalls für ein mit und alle hinreichend großen  gilt:
Dann folgt:
Beispiel
Aus der Formel ist folgendes abzulesen:
  ,
  
  
  ,
  
  
  ,
  
  
1. Bedingung:  
für ein 
 für ein 
Werte einsetzen:
Wähle : 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[Bearbeiten | Quelltext bearbeiten]

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:

  ,  
Für den 3. Fall ist zu zeigen:
Definition vom Ω-Kalkül:
Angewandt auf :
Widerspruch!
Es existiert kein , so dass 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 die hinreichende Bedingung erfüllt, gilt nun:
Siehe zu demselben Beispiel auch die Aufwandsabschätzung im Ο-Kalkül mit Hilfe der Substitutionsmethode.

Bemerkungen[Bearbeiten | Quelltext bearbeiten]

  • Angenommen, es ist folgende Rekurrenz gegeben, bei der 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[Bearbeiten | Quelltext bearbeiten]

In allgemeinerer Form gilt auch:

Definition[Bearbeiten | Quelltext bearbeiten]

Sei die zu untersuchende Abbildung der Form

,

wobei , und mit .

wird hierfür implizit durch oder für auf die reellen Zahlen fortgesetzt.

Dann gilt:

Literatur[Bearbeiten | Quelltext bearbeiten]