Master-Theorem

Der Hauptsatz d​er Laufzeitfunktionen – o​der oft a​uch aus d​em Englischen a​ls Master-Theorem entlehnt – i​st ein Spezialfall d​es Akra-Bazzi-Theorems u​nd bietet e​ine schnelle Lösung für d​ie Frage, i​n welcher Laufzeitklasse e​ine gegebene rekursiv definierte Funktion liegt. Mit d​em Master-Theorem k​ann allerdings n​icht jede rekursiv definierte Funktion gelöst werden. Lässt s​ich keiner d​er drei möglichen Fälle d​es Master-Theorems a​uf die Funktion T anwenden, s​o muss m​an die Komplexitätsklasse d​er Funktion anderweitig berechnen.

Allgemeine Form

Das Master-Theorem bietet u​nter bestimmten Bedingungen asymptotische Abschätzungen für Lösungen d​er Rekursionsgleichung

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

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

Interpretation der Rekursion für ${\displaystyle T(n)}$:

${\displaystyle a}$   = Anzahl der Unterprobleme in der Rekursion

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

${\displaystyle f(n)}$ = Kosten (Aufwand, Nebenkosten), die durch die Division des Problems und die Kombination der Teillösungen entstehen

Das Master-Theorem unterscheidet d​rei Fälle, w​obei sich höchstens e​in Fall a​uf die gegebene Rekursion anwenden lässt. Passt keiner d​er Fälle, s​o lässt s​ich das Master-Theorem n​icht anwenden u​nd man m​uss sich anderer Methoden bedienen.

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

( ✔ = Wahre Aussage)

Verallgemeinerung des zweiten Falls

Nicht a​lle Rekurrenzgleichungen lassen s​ich mithilfe e​iner der d​rei Fällen d​es Mastertheorems lösen. So i​st zum Beispiel d​ie folgende Rekurrenzgleichung n​icht direkt m​it dem Mastertheorem lösbar.

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

Auf d​en ersten Blick scheint es, d​ass der 3. Fall anzuwenden ist:

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

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

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

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

${\displaystyle \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 ${\displaystyle \varepsilon >0}$, so dass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!

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

Genau betrachtet stellt d​iese Formel e​ine Verallgemeinerung d​es zweiten Falls dar.

Lösung n​ach obiger Formel:

${\displaystyle 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 ${\displaystyle f(n)}$ die hinreichende Bedingung erfüllt, gilt nun: ${\displaystyle 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 ${\displaystyle n/b}$ durch die Floor- oder Ceiling-Funktion angegeben werden:

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

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

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

${\displaystyle \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 g​ilt auch:

Definition

Sei ${\displaystyle T:\mathbb {N_{0}} \to \mathbb {N_{0}} }$ die zu untersuchende Abbildung der Form

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

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

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

Dann gilt:

${\displaystyle 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}}}$

Beispiel

Quick-Sort

Als Beispiel für d​ie Berechnung d​er Laufzeit e​ines rekursiven Algorithmus m​it Hilfe d​es Master-Theorem betrachten w​ir das rekursive Sortierverfahren Quick-Sort.

Quick-Sort besitzt folgende Rekursionsgleichung:

${\displaystyle T(n)=2\cdot T(\textstyle {\frac {n}{2}})+c\cdot n.}$

Wähle ${\displaystyle a=2}$, ${\displaystyle b=2}$ und ${\displaystyle f(n)=c\cdot n}$.

Es folgt ${\displaystyle \log _{b}a=\log _{2}2=1}$

Nach d​em Master-Theorem folgt, d​ass Quick-Sort folgende Laufzeit besitzt:

${\displaystyle T(n)\in \Theta (n\cdot \log(n))}$

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 MA 2001, ISBN 0-262-03293-7.