Het master-theorem biedt een methode (master-method) die het bepalen van de looptijd van recurrente betrekkingen in de algoritmiek gemakkelijk maakt. Het master-theorem kan echter niet de complexiteit van alle recurrente betrekkingen bepalen.
Als voor het berekenen van een probleem van grootte
n
{\displaystyle n}
het probleem wordt opgedeeld in
a
{\displaystyle a}
deelproblemen ter grootte van
n
/
b
{\displaystyle n/b}
, waarin
a
≥
1
{\displaystyle a\geq 1}
en
b
>
1
{\displaystyle b>1}
, heeft de looptijd de vorm
-
T
(
n
)
=
a
⋅
T
(
n
b
)
+
f
(
n
)
{\displaystyle T(n)=a\cdot T\!\left({\frac {n}{b}}\right)+f(n)}
.
Daarin is
f
(
n
)
{\displaystyle f(n)}
de benodigde tijd voor de aanroep van de formule.
Men onderscheidt drie gevallen in het master-theorem. Welk geval van toepassing is, is afhankelijk van de verhouding tussen
f
(
n
)
{\displaystyle f(n)}
en
n
log
b
a
{\displaystyle n^{\log _{b}a}}
.
- Geval 1: als
n
log
b
a
>
f
(
n
)
{\displaystyle n^{\log _{b}a}>f(n)}
, dan
T
(
n
)
=
Θ
(
n
log
b
a
)
{\displaystyle T(n)=\Theta (n^{\log _{b}a})}
;
- Geval 2: als
n
log
b
a
=
f
(
n
)
{\displaystyle n^{\log _{b}a}=f(n)}
, dan
T
(
n
)
=
Θ
(
n
log
b
a
log
n
)
{\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}
;
- Geval 3: als
n
log
b
a
<
f
(
n
)
{\displaystyle n^{\log _{b}a}<f(n)}
, dan
T
(
n
)
=
Θ
(
f
(
n
)
)
{\displaystyle T(n)=\Theta (f(n))}
.
In dit geval is
n
log
b
a
>
f
(
n
)
{\displaystyle n^{\log _{b}a}>f(n)}
, dus dient
f
(
n
)
{\displaystyle f(n)}
polynomiaal kleiner te zijn dan
n
log
b
a
{\displaystyle n^{\log _{b}a}}
. Formeel gezegd:
f
(
n
)
=
O
(
n
log
b
a
−
ϵ
)
{\displaystyle f(n)=O(n^{\log _{b}a-\epsilon })}
voor een
ϵ
>
0
{\displaystyle \epsilon >0}
. Dit kan men ook nog uitdrukken als
lim
n
→
∞
n
log
b
a
f
(
n
)
=
lim
n
→
∞
n
ϵ
{\displaystyle {\underset {n\rightarrow \infty }{\lim }}{\frac {n^{\log _{b}a}}{f(n)}}={\underset {n\rightarrow \infty }{\lim }}n^{\epsilon }}
Voor een zekere
ϵ
>
0
{\displaystyle \epsilon >0}
.
Als daaraan wordt voldaan, dan volgt dat
T
(
n
)
=
Θ
(
n
log
b
a
)
{\displaystyle T(n)=\Theta (n^{\log _{b}a})}
Zij
T
(
n
)
=
9
T
(
n
3
)
+
n
{\displaystyle T(n)=9T({\frac {n}{3}})+n}
. Dan is
a
=
9
{\displaystyle a=9}
,
b
=
3
{\displaystyle b=3}
,
f
(
n
)
=
n
{\displaystyle f(n)=n}
en
n
log
b
a
=
n
2
{\displaystyle n^{\log _{b}a}=n^{2}}
. Zoals duidelijk te zien is, is
n
log
b
a
{\displaystyle n^{\log _{b}a}}
groter dan
f
(
n
)
{\displaystyle f(n)}
. In de formele voorwaarde valt dit goed te zien door
ϵ
=
1
{\displaystyle \epsilon =1}
te nemen.
Er geldt dus
T
(
n
)
=
Θ
(
n
log
b
a
)
=
Θ
(
n
2
)
{\displaystyle T(n)=\Theta (n^{\log _{b}a})=\Theta (n^{2})}
. De bovenstaande functie is dus in
Θ
(
n
2
)
{\displaystyle \Theta (n^{2})}
.
In dit geval is
n
log
b
a
=
f
(
n
)
{\displaystyle n^{\log _{b}a}=f(n)}
en dient
f
(
n
)
{\displaystyle f(n)}
gelijk te zijn aan
n
log
b
a
{\displaystyle n^{\log _{b}a}}
. Of formeel gezegd,
f
(
n
)
=
Θ
(
n
log
b
a
)
{\displaystyle f(n)=\Theta (n^{\log _{b}a})}
.
Als daaraan wordt voldaan, dan volgt daaruit dat
T
(
n
)
=
Θ
(
n
log
b
a
log
n
)
{\displaystyle T(n)=\Theta (n^{\log _{b}a}\log n)}
.
Zij
T
(
n
)
=
2
T
(
n
2
)
+
n
{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n}
. Dan is
a
=
2
{\displaystyle a=2}
,
b
=
2
{\displaystyle b=2}
,
f
(
n
)
=
n
{\displaystyle f(n)=n}
en
n
log
b
a
=
n
{\displaystyle n^{\log _{b}a}=n}
. Zoals te zien is, is
f
(
n
)
{\displaystyle f(n)}
gelijk aan
n
log
b
a
{\displaystyle n^{\log _{b}a}}
. Formeel: :
f
(
n
)
=
Θ
(
n
log
b
a
)
=
Θ
(
n
)
{\displaystyle f(n)=\Theta (n^{\log _{b}a})=\Theta (n)}
.
Er geldt dus
-
T
(
n
)
=
Θ
(
n
log
b
a
log
n
)
=
Θ
(
n
log
n
)
{\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\log n\right)=\Theta (n\log n)}
.
De bovenstaande functie is dus in
Θ
(
n
log
n
)
{\displaystyle \Theta (n\log n)}
.
In dit geval is
n
log
b
a
<
f
(
n
)
{\displaystyle n^{\log _{b}a}<f(n)}
en dient
f
(
n
)
{\displaystyle f(n)}
polynomiaal groter te zijn dan
n
log
b
a
{\displaystyle n^{\log _{b}a}}
. Formeel gezegd:
-
f
(
n
)
=
Ω
(
n
log
b
a
+
ϵ
)
{\displaystyle f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right)}
voor een
ϵ
>
0
{\displaystyle \epsilon >0}
.
De uitdrukking met limieten is dan
-
lim
n
→
∞
f
(
n
)
n
log
b
a
=
lim
n
→
∞
n
ϵ
{\displaystyle {\underset {n\rightarrow \infty }{\lim }}{\frac {f(n)}{n^{\log _{b}a}}}={\underset {n\rightarrow \infty }{\lim }}n^{\epsilon }}
Voor geval 3 geldt daarnaast een tweede voorwaarde, de regulariteitsvoorwaarde. Er dient te gelden dat
a
⋅
f
(
n
b
)
≤
c
⋅
f
(
n
)
{\displaystyle a\cdot f\!\left({\frac {n}{b}}\right)\leq c\cdot f(n)}
voor een
0
<
c
<
1
{\displaystyle 0<c<1}
. Als dit niet geldt, kan de looptijd niet met het master-theorem bepaald worden.
Als er aan deze voorwaarden wordt voldaan, volgt daaruit dat
T
(
n
)
=
Θ
(
f
(
n
)
)
{\displaystyle T(n)=\Theta (f(n))}
.
Zij
T
(
n
)
=
3
T
(
n
4
)
+
n
log
n
{\displaystyle T(n)=3T\left({\frac {n}{4}}\right)+n\log n}
. Dan is
a
=
3
{\displaystyle a=3}
,
b
=
4
{\displaystyle b=4}
,
f
(
n
)
=
n
log
n
{\displaystyle f(n)=n\log n}
en
n
log
b
a
≈
n
0
,
79
{\displaystyle n^{\log _{b}a}\approx n^{0,79}}
. Hier is dus
f
(
n
)
{\displaystyle f(n)}
groter dan
n
log
b
a
{\displaystyle n^{\log _{b}a}}
.
Nu moet er nog gecontroleerd worden of de regulariteitsvoorwaarde geldt:
-
a
f
(
n
b
)
≤
c
f
(
n
)
{\displaystyle af\left({\frac {n}{b}}\right)\leq cf(n)}
(voor c<1), het substitueren van de bekende variabelen levert op:
-
3
(
n
4
)
log
(
n
4
)
≤
c
n
log
n
{\displaystyle 3({\frac {n}{4}})\log({\frac {n}{4}})\leq c\;n\log n}
(voor c<1). Als er voor
c
{\displaystyle c}
bijvoorbeeld het getal
3
4
{\displaystyle {\frac {3}{4}}}
wordt genomen, dan is er dus aan de regulariteitsvoorwaarde voldaan.
Omdat er aan beide voorwaarden is voldaan, geldt er dus
T
(
n
)
=
Θ
(
f
(
n
)
)
=
Θ
(
n
log
n
)
{\displaystyle T(n)=\Theta (f(n))=\Theta (n\log n)}
. De bovenstaande functie is dus in
Θ
(
n
log
n
)
{\displaystyle \Theta (n\log n)}
.
Er zijn recurrente betrekkingen van de vorm
T
(
n
)
=
a
T
(
n
b
)
+
f
(
n
)
{\displaystyle T(n)=aT\left({\frac {n}{b}}\right)+f(n)}
waarvan de looptijd niet met deze methode bepaald kan worden, omdat niet aan de regulariteitsvoorwaarde wordt voldaan of omdat
f
(
n
)
{\displaystyle f(n)}
niet polynomiaal groter of kleiner is dan
n
log
b
a
{\displaystyle n^{\log _{b}a}}
.
Beschouw de formule
T
(
n
)
=
2
T
(
n
2
)
+
n
log
n
{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+n\log n}
. Hier is a=2, b=2,
f
(
n
)
=
n
log
n
{\displaystyle f(n)=n\log n}
en
n
log
b
a
=
n
{\displaystyle n^{\log _{b}a}=n}
. Het is duidelijk dat
f
(
n
)
=
Ω
(
n
)
{\displaystyle f(n)=\Omega (n)}
, dus zitten we in het derde geval. Echter,
-
lim
n
→
∞
n
log
n
n
=
lim
n
→
∞
log
n
{\displaystyle {\underset {n\rightarrow \infty }{\lim }}{\frac {n\log n}{n}}={\underset {n\rightarrow \infty }{\lim }}\log n}
Er bestaat geen enkele
ϵ
>
0
{\displaystyle \epsilon >0}
zodat
log
n
=
n
ϵ
{\displaystyle \log n=n^{\epsilon }}
, en dus kan de master theorem niet worden toegepast.
Bronnen, noten en/of referenties
- Met de logaritmische functies in dit artikel worden logaritmes bedoeld met grondgetal 2 (lb volgens ISO 31-11).