Der Hauptsatz der Laufzeitfunktionen – oder oft auch aus dem Englischen als Master-Theorem entlehnt – ist ein Spezialfall des Akra-Bazzi-Theorems und bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt. Mit dem Master-Theorem kann allerdings 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.
Das Master-Theorem bietet unter bestimmten Bedingungen asymptotische Abschätzungen für Lösungen der Rekursionsgleichung
T
(
n
)
=
a
⋅
T
(
n
b
)
+
f
(
n
)
.
{\displaystyle T(n)=a\cdot T(\textstyle {\frac {n}{b}})+f(n).}
Hierbei steht
T
(
n
)
{\displaystyle T(n)}
a
{\displaystyle a}
b
{\displaystyle b}
f
(
n
)
{\displaystyle f(n)}
T
(
n
)
{\displaystyle T(n)}
a
≥
1
{\displaystyle a\geq 1}
b
>
1
{\displaystyle b>1}
Interpretation der Rekursion für
T
(
n
)
{\displaystyle T(n)}
a
{\displaystyle a}
1
/
b
{\displaystyle 1/b}
f
(
n
)
{\displaystyle f(n)}
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
f
(
n
)
∈
O
(
n
log
b
a
−
ε
)
{\displaystyle f(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)}
ε
>
0
{\displaystyle \varepsilon >0}
f
(
n
)
∈
Θ
(
n
log
b
a
)
{\displaystyle f(n)\in \Theta \left(n^{\log _{b}a}\right)}
f
(
n
)
∈
Ω
(
n
log
b
a
+
ε
)
{\displaystyle f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)}
ε
>
0
{\displaystyle \varepsilon >0}
und ebenfalls für ein
c
{\displaystyle c}
0
<
c
<
1
{\displaystyle 0<c<1}
n
{\displaystyle n}
a
f
(
n
b
)
≤
c
f
(
n
)
{\displaystyle af(\textstyle {\frac {n}{b}})\leq cf(n)}
Dann folgt:
T
(
n
)
∈
Θ
(
n
log
b
a
)
{\displaystyle T(n)\in \Theta \left(n^{\log _{b}a}\right)}
T
(
n
)
∈
Θ
(
n
log
b
a
log
(
n
)
)
{\displaystyle T(n)\in \Theta \left(n^{\log _{b}a}\log(n)\right)}
T
(
n
)
∈
Θ
(
f
(
n
)
)
{\displaystyle T(n)\in \Theta (f(n))}
Beispiel
T
(
n
)
=
8
T
(
n
2
)
+
1000
n
2
{\displaystyle T(n)=8T(\textstyle {\frac {n}{2}})+1000n^{2}}
T
(
n
)
=
2
T
(
n
2
)
+
10
n
{\displaystyle T(n)=2T(\textstyle {\frac {n}{2}})+10n}
T
(
n
)
=
2
T
(
n
2
)
+
n
2
{\displaystyle T(n)=2T(\textstyle {\frac {n}{2}})+n^{2}}
Aus der Formel ist folgendes abzulesen:
a
=
8
{\displaystyle a=8}
b
=
2
{\displaystyle b=2}
f
(
n
)
=
1000
n
2
{\displaystyle f(n)=1000n^{2}}
log
b
a
=
log
2
8
=
3
{\displaystyle \log _{b}a=\log _{2}8=3}
a
=
2
{\displaystyle a=2}
b
=
2
{\displaystyle b=2}
f
(
n
)
=
10
n
{\displaystyle f(n)=10n}
log
b
a
=
log
2
2
=
1
{\displaystyle \log _{b}a=\log _{2}2=1}
a
=
2
{\displaystyle a=2}
b
=
2
{\displaystyle b=2}
f
(
n
)
=
n
2
{\displaystyle f(n)=n^{2}}
log
b
a
=
log
2
2
=
1
{\displaystyle \log _{b}a=\log _{2}2=1}
1. Bedingung:
f
(
n
)
∈
O
(
n
log
b
a
−
ε
)
{\displaystyle f(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)}
ε
>
0
{\displaystyle \varepsilon >0}
f
(
n
)
∈
Θ
(
n
log
b
a
)
{\displaystyle f(n)\in \Theta \left(n^{\log _{b}a}\right)}
f
(
n
)
∈
Ω
(
n
log
b
a
+
ε
)
{\displaystyle f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)}
ε
>
0
{\displaystyle \varepsilon >0}
Werte einsetzen:
1000
n
2
∈
O
(
n
3
−
ε
)
{\displaystyle 1000n^{2}\in {\mathcal {O}}\left(n^{3-\varepsilon }\right)}
10
n
∈
Θ
(
n
1
)
{\displaystyle 10n\in \Theta \left(n^{1}\right)}
n
2
∈
Ω
(
n
1
+
ε
)
{\displaystyle n^{2}\in \Omega \left(n^{1+\varepsilon }\right)}
Wähle
ε
>
0
{\displaystyle \varepsilon >0}
1000
n
2
∈
O
(
n
2
)
{\displaystyle 1000n^{2}\in {\mathcal {O}}\left(n^{2}\right)}
ε
=
1
{\displaystyle \varepsilon =1}
✔
10
n
∈
Θ
(
n
)
{\displaystyle 10n\in \Theta \left(n\right)}
✔
n
2
∈
Ω
(
n
2
)
{\displaystyle n^{2}\in \Omega \left(n^{2}\right)}
ε
=
1
{\displaystyle \varepsilon =1}
✔
2. Bedingung: (nur im 3. Fall)
a
f
(
n
b
)
≤
c
f
(
n
)
{\displaystyle af(\textstyle {\frac {n}{b}})\leq cf(n)}
Setze auch hier obige Werte ein:
2
(
n
2
)
2
≤
c
n
2
⇔
{\displaystyle 2(\textstyle {\frac {n}{2}})^{2}\leq cn^{2}\Leftrightarrow }
1
2
n
2
≤
c
n
2
{\displaystyle \textstyle {\frac {1}{2}}n^{2}\leq cn^{2}}
Wähle c = ½:
∀
n
≥
1
:
1
2
n
2
≤
1
2
n
2
{\displaystyle \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
)
∈
Θ
(
n
3
)
{\displaystyle T(n)\in \Theta (n^{3})}
T
(
n
)
∈
Θ
(
n
log
(
n
)
)
{\displaystyle T(n)\in \Theta (n\log(n))}
T
(
n
)
∈
Θ
(
n
2
)
{\displaystyle T(n)\in \Theta (n^{2})}
( ✔ = Wahre Aussage)
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
(
n
2
)
+
n
3
ln
(
n
)
{\displaystyle 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
,
{\displaystyle a=8,}
b
=
2
{\displaystyle b=2}
f
(
n
)
=
n
3
ln
(
n
)
{\displaystyle f(n)=n^{3}\ln(n)}
Für den 3. Fall ist zu zeigen:
f
(
n
)
∈
Ω
(
n
log
b
a
+
ε
)
{\displaystyle f(n)\in \Omega \left(n^{\log _{b}a+\varepsilon }\right)}
Definition vom Ω-Kalkül :
f
(
n
)
∈
Ω
(
g
(
n
)
)
:
0
<
lim inf
n
→
∞
|
f
(
n
)
g
(
n
)
|
≤
∞
{\displaystyle 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
)
∈
Ω
(
n
log
2
8
+
ε
)
{\displaystyle n^{3}\ln(n)\in \Omega \left(n^{\log _{2}8+\varepsilon }\right)}
∃
ε
>
0
:
0
<
lim inf
n
→
∞
|
f
(
n
)
g
(
n
)
|
=
lim inf
n
→
∞
|
n
3
ln
(
n
)
n
log
2
8
+
ε
|
=
lim inf
n
→
∞
|
ln
(
n
)
n
ε
|
=
0
⇒
{\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 }
Es existiert kein
ε
>
0
{\displaystyle \varepsilon >0}
Es gilt:
T
(
n
)
∈
Θ
(
n
log
b
a
ln
k
+
1
n
)
{\displaystyle T(n)\in \Theta \left(n^{\log _{b}a}\ln ^{k+1}n\right)}
f
(
n
)
∈
Θ
(
n
log
b
a
ln
k
n
)
{\displaystyle 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
)
∈
Θ
(
n
log
b
a
ln
k
n
)
=
Θ
(
n
log
2
8
ln
1
n
)
=
Θ
(
n
3
ln
(
n
)
)
{\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
f
(
n
)
{\displaystyle f(n)}
T
(
n
)
=
Θ
(
n
3
ln
2
n
)
{\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 . Angenommen, es ist folgende Rekurrenz gegeben, bei der
n
/
b
{\displaystyle n/b}
Floor- oder Ceiling-Funktion angegeben werden: z. B.:
T
(
n
)
=
a
T
(
⌊
n
b
⌋
)
+
f
(
n
)
{\displaystyle T(n)=aT(\lfloor {\tfrac {n}{b}}\rfloor )+f(n)}
In diesem Fall kann man
⌊
n
b
⌋
{\displaystyle \lfloor {\tfrac {n}{b}}\rfloor }
⌈
n
b
⌉
{\displaystyle \lceil {\tfrac {n}{b}}\rceil }
n
b
{\displaystyle {\tfrac {n}{b}}}
Ob man nun
T
(
n
)
∈
Θ
(
ln
(
n
)
)
{\displaystyle T(n)\in \Theta (\ln(n))}
T
(
n
)
∈
Θ
(
lg
(
n
)
)
{\displaystyle T(n)\in \Theta (\lg(n))}
Logarithmengesetzen gilt:
ln
(
n
)
=
log
e
(
n
)
=
log
10
(
n
)
log
10
(
e
)
=
c
⋅
log
10
n
∈
Θ
(
log
10
n
)
=
Θ
(
lg
n
)
{\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})}
In allgemeinerer Form gilt auch:
Sei
T
:
N
0
→
N
0
{\displaystyle T:\mathbb {N_{0}} \to \mathbb {N_{0}} }
T
(
n
)
=
∑
i
=
1
m
T
(
α
i
n
)
+
f
(
n
)
{\displaystyle T(n)=\sum _{i=1}^{m}T\left(\alpha _{i}n\right)+f(n)}
wobei
α
i
∈
R
:
0
<
α
i
<
1
{\displaystyle \alpha _{i}\in \mathbb {R} :0<\alpha _{i}<1}
m
∈
N
:
m
≥
1
{\displaystyle m\in \mathbb {N} :m\geq 1}
f
(
n
)
∈
Θ
(
n
k
)
{\displaystyle f(n)\in \Theta (n^{k})}
k
∈
N
0
{\displaystyle k\in \mathbb {N_{0}} }
T
{\displaystyle T}
T
(
x
)
:=
T
(
⌊
x
⌋
)
{\displaystyle T(x):=T(\lfloor x\rfloor )}
T
(
⌈
x
⌉
)
{\displaystyle T(\lceil x\rceil )}
x
∈
R
0
+
{\displaystyle x\in \mathbb {R_{0}^{+}} }
Dann gilt:
T
(
n
)
∈
{
Θ
(
n
k
)
falls
∑
i
=
1
m
(
α
i
k
)
<
1
Θ
(
n
k
log
n
)
falls
∑
i
=
1
m
(
α
i
k
)
=
1
Θ
(
n
c
)
mit
∑
i
=
1
m
(
α
i
c
)
=
1
falls
∑
i
=
1
m
(
α
i
k
)
>
1
{\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}}}
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 . 
