Master-Theorem

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

Das Master-Theorem leitet unter bestimmten Bedingungen asymptotische Abschätzungen für Lösungen der Rekursionsgleichung

$T(n)=a\cdot T(\textstyle {\frac {n}{b}})+f(n).$

Hierbei steht $T(n)$ für die gesuchte Laufzeitfunktion, während $a$ und $b$ Konstanten sind. Ferner bezeichnet $f(n)$ eine von $T(n)$ unabhängige und nicht negative Funktion. Damit das Master-Theorem angewendet werden kann, müssen für die beiden Konstanten die Bedingungen $a\geq 1$ und $b>1$ erfüllt sein.

Interpretation der Rekursion für $T(n)$:

$a$   = Anzahl der Unterprobleme in der Rekursion

$1/b$ = Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird

$f(n)$ = 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(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)$  für ein $\varepsilon >0$	$f(n)\in \Theta \left(n^{\log _{b}a}\right)$	$f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)$ für ein $\varepsilon >0$ und ebenfalls für ein $c$ mit $0<c<1$ und alle hinreichend großen $n$ gilt: $af(\textstyle {\frac {n}{b}})\leq cf(n)$
Dann folgt:	$T(n)\in \Theta \left(n^{\log _{b}a}\right)$	$T(n)\in \Theta \left(n^{\log _{b}a}\log(n)\right)$	$T(n)\in \Theta (f(n))$
Beispiel	$T(n)=8T(\textstyle {\frac {n}{2}})+1000n^{2}$	$T(n)=2T(\textstyle {\frac {n}{2}})+10n$	$T(n)=2T(\textstyle {\frac {n}{2}})+n^{2}$
Aus der Formel ist folgendes abzulesen:	$a=8$, $b=2$   $f(n)=1000n^{2}$   $\log _{b}a=\log _{2}8=3$	$a=2$, $b=2$   $f(n)=10n$   $\log _{b}a=\log _{2}2=1$	$a=2$, $b=2$   $f(n)=n^{2}$   $\log _{b}a=\log _{2}2=1$
1. Bedingung:	$f(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)$  für ein $\varepsilon >0$	$f(n)\in \Theta \left(n^{\log _{b}a}\right)$	$f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)$ für ein $\varepsilon >0$
Werte einsetzen:	$1000n^{2}\in {\mathcal {O}}\left(n^{3-\varepsilon }\right)$	$10n\in \Theta \left(n^{1}\right)$	$n^{2}\in \Omega \left(n^{1+\varepsilon }\right)$
Wähle $\varepsilon >0$:	$1000n^{2}\in {\mathcal {O}}\left(n^{2}\right)$ mit $\varepsilon =1$  ✔	$10n\in \Theta \left(n\right)$  ✔	$n^{2}\in \Omega \left(n^{2}\right)$ mit $\varepsilon =1$  ✔
2. Bedingung: (nur im 3. Fall)			$af(\textstyle {\frac {n}{b}})\leq cf(n)$ Setze auch hier obige Werte ein: $2(\textstyle {\frac {n}{2}})^{2}\leq cn^{2}\Leftrightarrow$$\textstyle {\frac {1}{2}}n^{2}\leq cn^{2}$ Wähle c = ½: $\forall n\geq 1:\textstyle {\frac {1}{2}}n^{2}\leq \textstyle {\frac {1}{2}}n^{2}$  ✔
Damit gilt für die Laufzeitfunktion:	$T(n)\in \Theta (n^{3})$	$T(n)\in \Theta (n\log(n))$	$T(n)\in \Theta (n^{2})$

( ✔ = Wahre Aussage )

Verallgemeinerung des zweiten Falls

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.

$T(n)=8T(\textstyle {\frac {n}{2}})+n^{3}\ln(n)$.

Auf den ersten Blick scheint es, dass der 3. Fall anzuwenden ist:

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

Für den 3. Fall ist zu zeigen: $f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)$

Definition vom Ω-Kalkül:$f(n)\in \Omega (g(n)):0<\liminf _{n\to \infty }\left|\textstyle {\frac {f(n)}{g(n)}}\right|\leq \infty$

Angewandt auf $n^{3}\ln(n)\in \Omega \left(n^{\log _{2}8+\varepsilon }\right)$:

$\exists \varepsilon >0:0<\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|=\liminf _{n\to \infty }\left|{\frac {n^{3}\ln(n)}{n^{\log _{2}8+\varepsilon }}}\right|=\liminf _{n\to \infty }\left|{\frac {\ln(n)}{n^{\varepsilon }}}\right|=0\Rightarrow$ Widerspruch!

Es existiert kein $\varepsilon >0$, so dass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!

Es gilt: $T(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k+1}n\right)$, falls $f(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k}n\right)$

Genau betrachtet stellt diese Formel eine Verallgemeinerung des zweiten Falls dar.

Lösung nach obiger Formel:

$f(n)=n^{3}\ln(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k}n\right)=\Theta \left(n^{\log _{2}8}\ln ^{1}n\right)=\Theta \left(n^{3}\ln(n)\right)$ ✔

Da $f(n)$ die hinreichende Bedingung erfüllt, gilt nun: $T(n)=\Theta \left(n^{3}\ln ^{2}n\right)$

Siehe zu demselben Beispiel auch die Aufwandsabschätzung im Ο-Kalkül mit Hilfe der Substitutionsmethode.

Bemerkungen

• Angenommen, es ist folgende Rekurrenz gegeben, bei der $n/b$ durch die Floor- oder Ceiling-Funktion angegeben werden:

z. B.:  $T(n)=aT(\lfloor {\tfrac {n}{b}}\rfloor )+f(n)$

In diesem Fall kann man $\lfloor {\tfrac {n}{b}}\rfloor$ oder auch $\lceil {\tfrac {n}{b}}\rceil$ mit Hilfe der Form ${\tfrac {n}{b}}$ abschätzen.

• Ob man nun $T(n)\in \Theta (\ln(n))$  (Logarithmus naturalis) schreibt, oder  $T(n)\in \Theta (\lg(n))$ (dekadischer Logarithmus) ist egal, da nach den Logarithmengesetzen gilt:

$\ln(n)=\log _{e}(n)=\textstyle {\frac {\log _{10}(n)}{\log _{10}(e)}}=c\cdot \log _{10}{n}\in \Theta (\log _{10}{n})=\Theta (\lg {n})$

Allgemeinere Form

In allgemeinerer Form gilt auch:

Definition

Sei $T:\mathbb {N} \to \mathbb {N}$ die zu untersuchende Abbildung der Form

$T(n)=\sum _{i=1}^{m}T\left(\alpha _{i}n\right)+f(n)$,

wobei $\alpha _{i}\in \mathbb {R} :0<\alpha _{i}<1$, $m\in \mathbb {N} :m\geq 1$ und $f(n)\in \Theta (n^{k})$ mit $k\in \mathbb {N} :k\geq 0$.

$T$ wird hierfür implizit durch $T(x):=T(\lfloor x\rfloor )$ oder $T(\lceil x\rceil )$ für $x\in \mathbb {R^{+}}$ auf die reellen Zahlen fortgesetzt.

Dann gilt:

$T(n)\in {\begin{cases}\Theta (n^{k})&{\mbox{falls }}\sum _{i=1}^{m}(\alpha _{i}^{k})<1\\\Theta (n^{k}\log n)&{\mbox{falls }}\sum _{i=1}^{m}(\alpha _{i}^{k})=1\\\Theta (n^{c}){\mbox{ mit }}\sum _{i=1}^{m}(\alpha _{i}^{c})=1&{\mbox{falls }}\sum _{i=1}^{m}(\alpha _{i}^{k})>1\end{cases}}$

Literatur

• Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Algorithmen – eine Einführung. Oldenbourg, München, Wien 2004, ISBN 3-486-27515-1 (Originaltitel: Introduction to algorithms. Übersetzt von Karen Lippert, Micaela Krieger-Hauwede). 
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Introduction to Algorithms. 2. Auflage. MIT Press, Cambridge (Massachusetts) 2001, ISBN 0-262-03293-7.