Master-Theorem

Der Begriff 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

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

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

Hierbei steht T(n) für die zu untersuchende 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, muss für die beiden Konstanten die Bedingung a ≥ 1 und b > 1 erfüllt sein.

Interpretation der Rekurrenz 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), die durch die Division des Problems und der Kombination der Teillösungen entstehen

Weiterhin benötigt man für die Benutzung des Master-Theorems noch den Logarithmus von a zur Basis b, log _ba.

Das Master-Theorem unterscheidet sich in 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 ε > 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 ε > 0 und ebenfalls für ein c mit 0 < c < 1 und alle hinreichend großen n gilt: $a f( \textstyle \frac{n}{b} ) \le c f(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) = 8 T(\textstyle \frac{n}{2}) + 1000n^2$	$T(n) = 2 T(\textstyle \frac{n}{2}) + 10n$	$T(n) = 2 T(\textstyle \frac{n}{2}) + n^2$
Aus der Formel ist folgendes abzulesen:	a = 8, b = 2   f(n) = 1000n2   log ba = log 28 = 3	a = 2, b = 2   f(n) = 10n   log ba = log 22 = 1	a = 2, b = 2   f(n) = n2   log ba = log 22 = 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)			$a f(\textstyle \frac{n}{b} ) \le c f(n)$ Setze auch hier obige Werte ein: $2 (\textstyle \frac{n}{2} )^2 \le c n^2 \Leftrightarrow$$\textstyle \frac{1}{2} n^2 \le cn^2$ Wähle c = ½: $\forall n \ge 1 : \textstyle \frac{1}{2} n^2 \le \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) = 8 T( \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³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| \le \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$, sodass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!

Es gilt: $T(n) = \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 notwendige 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) = a T( \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\sdot \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 \ge 1$ und $f(n) \in \Theta(n^k)$ mit $k \in \mathbb{N}: k \ge 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. 
• 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.