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)}
für die gesuchte Laufzeitfunktion, während
a
{\displaystyle a}
und
b
{\displaystyle b}
Konstanten sind. Ferner bezeichnet
f
(
n
)
{\displaystyle f(n)}
eine von
T
(
n
)
{\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
a
≥
1
{\displaystyle a\geq 1}
und
b
>
1
{\displaystyle b>1}
erfüllt sein.
Interpretation der Rekursion für
T
(
n
)
{\displaystyle T(n)}
:
a
{\displaystyle a}
= Anzahl der Unterprobleme in der Rekursion
1
/
b
{\displaystyle 1/b}
= Teil des Originalproblems, welches wiederum durch alle Unterprobleme repräsentiert wird
f
(
n
)
{\displaystyle 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
f
(
n
)
∈
O
(
n
log
b
a
−
ε
)
{\displaystyle f(n)\in {\mathcal {O}}\left(n^{\log _{b}a-\varepsilon }\right)}
für ein
ε
>
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)}
für ein
ε
>
0
{\displaystyle \varepsilon >0}
und ebenfalls für ein
c
{\displaystyle c}
mit
0
<
c
<
1
{\displaystyle 0<c<1}
und alle hinreichend großen
n
{\displaystyle n}
gilt:
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)}
für ein
ε
>
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)}
für ein
ε
>
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)}
mit
ε
=
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)}
mit
ε
=
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 }
Widerspruch!
Es existiert kein
ε
>
0
{\displaystyle \varepsilon >0}
, so dass der Limes ungleich Null ist. Also ist der 3. Fall nicht auf diese Rekursionsgleichung anwendbar!
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)}
, falls
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)}
die hinreichende Bedingung erfüllt, gilt nun:
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}
durch die 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 }
oder auch
⌈
n
b
⌉
{\displaystyle \lceil {\tfrac {n}{b}}\rceil }
mit Hilfe der Form
n
b
{\displaystyle {\tfrac {n}{b}}}
abschätzen.
Ob man nun
T
(
n
)
∈
Θ
(
ln
(
n
)
)
{\displaystyle T(n)\in \Theta (\ln(n))}
(Logarithmus naturalis) schreibt, oder
T
(
n
)
∈
Θ
(
lg
(
n
)
)
{\displaystyle T(n)\in \Theta (\lg(n))}
(dekadischer Logarithmus) ist egal, da nach den 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}} }
die zu untersuchende Abbildung der Form
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}
und
f
(
n
)
∈
Θ
(
n
k
)
{\displaystyle f(n)\in \Theta (n^{k})}
mit
k
∈
N
0
{\displaystyle k\in \mathbb {N_{0}} }
.
T
{\displaystyle T}
wird hierfür implizit durch
T
(
x
)
:=
T
(
⌊
x
⌋
)
{\displaystyle T(x):=T(\lfloor x\rfloor )}
oder
T
(
⌈
x
⌉
)
{\displaystyle T(\lceil x\rceil )}
für
x
∈
R
0
+
{\displaystyle x\in \mathbb {R_{0}^{+}} }
auf die reellen Zahlen fortgesetzt.
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}}}
Als Beispiel für die Berechnung der Laufzeit eines rekursiven Algorithmus mit Hilfe des Master-Theorem betrachten wir das rekursive Sortierverfahren Quick-Sort .
Quick-Sort besitzt folgende Rekursionsgleichung:
T
(
n
)
=
2
⋅
T
(
n
2
)
+
c
⋅
n
.
{\displaystyle T(n)=2\cdot T(\textstyle {\frac {n}{2}})+c\cdot n.}
Wähle
a
=
2
{\displaystyle a=2}
,
b
=
2
{\displaystyle b=2}
und
f
(
n
)
=
c
⋅
n
{\displaystyle f(n)=c\cdot n}
.
Es folgt
log
b
a
=
log
2
2
=
1
{\displaystyle \log _{b}a=\log _{2}2=1}
Nach dem Master-Theorem folgt, dass Quick-Sort folgende Laufzeit besitzt:
T
(
n
)
∈
Θ
(
n
⋅
log
(
n
)
)
{\displaystyle T(n)\in \Theta (n\cdot \log(n))}
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 .