Master-Theorem

Das Master-Theorem 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

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

$T(n)=aT\left({\frac {n}{b}}\right)+f(n)$

Hierbei steht T(n) für die zu gesamte zu untersuchende Laufzeitfunktion, während a und b Konstanten sind, die sich aus der konkret zu untersuchenden Laufzeitfunktion ergeben. Ferner bezeichnet f(n) eine Laufzeitfunktion welche jedoch nicht von der zu untersuchenden Funktion T(n) abhängt. Damit das Master-Theorem angewendet werden kann, muss für die beiden Konstanten die Bedingung erfüllt sein, dass a ≥ 1 und b > 1.

Weiterhin braucht man für die Benutzung des Master-Theorems noch den Logarithmus von a zur Basis b $\log _{b}a$, welchen man aus den beiden Größen a und b errechnen kann.

Erster Fall

Allgemein

Falls gilt:

$f(n)\in O\left(n^{\log _{b}a-\epsilon }\right)$ für ein $\epsilon >0$

dann folgt:

$T(n)\in \Theta \left(n^{\log _{b}a}\right).$

Beispiel

$T(n)=8T\left({\frac {n}{2}}\right)+1000n^{2}$

Wie man aus der Formel oben ablesen kann, gilt:

$a=8$, $b=2$, $f(n)=1000n^{2}$, $\log _{b}a=\log _{2}8=3$

Nun muss man überprüfen, ob gilt, dass

$f(n)\in O\left(n^{\log _{b}a-\epsilon }\right)$

Setzt man nun die Werte von oben ein, so ergibt sich:

$1000n^{2}\in O\left(n^{3-\epsilon }\right)$

Wählt man nun $\epsilon$ = 1, so folgt:

$1000n^{2}\in O\left(n^{3-1}\right)=O\left(n^{2}\right)$

Da diese Aussage wahr ist, trifft somit der erste Fall des Master-Theorems auf die gegebene Rekurrenzgleichung zu. Damit folgt nun:

$T(n)\in \Theta \left(n^{\log _{b}a}\right).$

Setzt man hier nun die Werte von oben ein, so ergibt sich:

$T(n)\in \Theta \left(n^{3}\right).$

Somit lag die gegebene Laufzeitfunktion T(n) in Θ(n³)

Zweiter Fall

Allgemein

Falls gilt:

$f(n)\in \Theta \left(n^{\log _{b}a}\right)$

dann folgt:

$T(n)\in \Theta \left(n^{\log _{b}a}\log(n)\right).$

Beispiel

$T(n)=2T\left({\frac {n}{2}}\right)+10n$

Wie man aus der Formel oben ablesen kann, gilt:

$a=2$, $b=2$, $f(n)=10n$, $\log _{b}a=\log _{2}2=1$

Nun muss man überprüfen ob gilt, dass

$f(n)\in \Theta \left(n^{\log _{b}a}\right)$

Setzt man nun die Werte von oben ein, so ergibt sich:

$10n\in \Theta \left(n^{1}\right)=\Theta \left(n\right)$

Da diese Aussage wahr ist trifft somit der zweite Fall des Master-Theorems auf die gegebene Rekurrenzgleichung zu. Damit folgt nun:

$T(n)\in \Theta \left(n^{\log _{b}a}\log(n)\right).$

Setzt man auch hier wieder die Werte ein, so erhält man:

$T(n)\in \Theta \left(n\log(n)\right).$

Somit lag die gegebene Laufzeitfunktion T(n) in Θ(nlog(n))

Dritter Fall

Allgemein

Falls gilt:

$f(n)\in \Omega \left(n^{\log _{b}a+\epsilon }\right)$ für ein $\epsilon >0$

und falls ebenfalls gilt:

$af\left({\frac {n}{b}}\right)\leq cf(n)$ für ein $c<1$ und genügend große n

dann folgt:

$T(n)\in \Theta (f(n)).$

Beispiel

$T(n)=2T\left({\frac {n}{2}}\right)+n^{2}$

Wie man aus der Formel oben ablesen kann, gilt:

$a=2$, $b=2$, $f(n)=n^{2}$, $\log _{b}a=\log _{2}2=1$

Nun muss man überprüfen ob gilt, dass

$f(n)\in \Omega \left(n^{\log _{b}a+\epsilon }\right)$

Setzt man nun die Werte von oben ein, und wählt $\epsilon$ = 1, so folgt:

$n^{2}\in \Omega \left(n^{1+1}\right)=\Omega \left(n^{2}\right)$

Da diese Aussage wahr ist muss nun noch die zweite Bedingung überprüft werden, nämlich ob gilt, dass

$af\left({\frac {n}{b}}\right)\leq cf(n)$

Setzt man auch hier wieder die Werte von oben ein, so ergibt sich:

$2\left({\frac {n}{2}}\right)^{2}$$\leq cn^{2}\Leftrightarrow {\frac {1}{2}}n^{2}\leq cn^{2}$

Wählt man nun $c={\frac {1}{2}}$, so gilt:

${\frac {1}{2}}n^{2}\leq {\frac {1}{2}}n^{2}$ $\forall n\geq 1$

Somit gilt

$T(n)\in \Theta (f(n)).$

Setzt man auch hier wieder die Werte ein, so erhält man:

$T(n)\in \Theta (n^{2}).$

Somit lag die gegebene Laufzeitfunktion T(n) in Θ(n²) was dem f(n) der Ausgangsformel entspricht.