Master-Theorem


Mit dem Master-Theorem, oder auch dem Hauptsatz der Laufzeitfunktionen genannt, kann man ermitteln, in welcher Laufzeitklasse eine gegebene rekursive Funktion liegt. Dafür existieren drei mögliche Fälle. Allerdings lassen sich nicht alle Funktionen in einer der drei Fälle einordnen. Damit dies nämlich möglich ist, ist folgende allgemeine Form für die Anwendung des Master-Theorems nötig:

Form des Master-Theorems

Dabei muss gelten, dass a größer gleich 1 ist und b größer als 1. In der Form sind a und b jeweils Konstanten, T(n) steht für die zu untersuchende Laufzeitfunktion und f(n) ist eine nicht negative Funktion die unabhängig von T(n) ist.

Nun gibt es folgende drei Fälle, wobei je Rekursion immer nur ein Fall zutrifft. Es kann auch sein, dass kein Fall zutrifft, dann ist das Master-Theorem nicht anwendbar und man muss zu einer anderen Methode greifen.

Fall 1

Falls gilt: Erster Fall des Master-Theorems mit ε > 0
dann folgt: Folgerung des ersten Falls des Master-Theorems

Fall 2

Falls gilt: Zweiter Fall des Master-Theorems
dann folgt: Folgerung des zweiten Falls des Master-Theorems

Fall 3

Falls gilt: Dritter Fall des Master-Theorems mit ε > 0 und für ein c mit 0 < c < 1 und allen hinreichend großen n zusätzlich gilt: Dritter Fall des Master-Theorems
dann folgt: Folgerung des dritten Falls des Master-Theorems

Grundsätzlich vergleicht man also in allen drei Fälle die Funktion f(n) mit n hoch log ba und die Lösung der Rekursion wird jeweils von der (asymptotisch) "größeren" der beiden Funktionen bestimmt. Mann kann also auch sagen:

Master-Theorem Beispiel

T(n) = 4T(n/2) + n2
Nun ist also a=4 und b=2. Eingesetzt ergibt das: nlog24 und das ist n2. Da f(n) ebenfalls n2 ist, ist dies also der zweite Fall und es gilt: Folgerung des zweiten Falls des Master-Theorems also Ergebnis erste Aufgabe Master-Theorem

Zitat:



Edsger Wybe Dijkstra:

"Als es noch keine Computer gab, gab es auch das Programmieren als Problem nicht. Als es dann ein paar leistungsschwache Computer gab, wurde das Programmieren zu einem kleinen Problem und nun, wo wir leistungsstarke Computer haben, ist auch das Programmieren zu einem riesigen Problem angewachsen. In diesem Sinne hat die elektronische Industrie kein einziges Problem gelöst, sondern nur neue geschaffen." - The Humble Programmer, ACM Turing Lecture 1972