Master-theorem

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.

Theorie

Als voor het berekenen van een probleem van grootte $n$ het probleem wordt opgedeeld in $a$ deelproblemen ter grootte van $n/b$, waarin $a\geq 1$ en $b>1$, heeft de looptijd de vorm

$T(n)=a\cdot T\!\left({\frac {n}{b}}\right)+f(n)$.

Daarin is $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)$ en $n^{\log _{b}a}$.

• Geval 1: als $n^{\log _{b}a}>f(n)$, dan $T(n)=\Theta (n^{\log _{b}a})$;
• Geval 2: als $n^{\log _{b}a}=f(n)$, dan $T(n)=\Theta (n^{\log _{b}a}\log n)$;
• Geval 3: als $n^{\log _{b}a}<f(n)$, dan $T(n)=\Theta (f(n))$.

Geval 1

In dit geval is $n^{\log _{b}a}>f(n)$, dus dient $f(n)$ polynomiaal kleiner te zijn dan $n^{\log _{b}a}$. Formeel gezegd: $f(n)=O(n^{\log _{b}a-\epsilon })$ voor een $\epsilon >0$. Dit kan men ook nog uitdrukken als

${\underset {n\rightarrow \infty }{\lim }}{\frac {n^{\log _{b}a}}{f(n)}}={\underset {n\rightarrow \infty }{\lim }}n^{\epsilon }$

Voor een zekere $\epsilon >0$.

Als daaraan wordt voldaan, dan volgt dat $T(n)=\Theta (n^{\log _{b}a})$

Voorbeeld

Zij $T(n)=9T({\frac {n}{3}})+n$. Dan is $a=9$, $b=3$, $f(n)=n$ en $n^{\log _{b}a}=n^{2}$. Zoals duidelijk te zien is, is $n^{\log _{b}a}$ groter dan $f(n)$ . In de formele voorwaarde valt dit goed te zien door $\epsilon =1$ te nemen.

Er geldt dus $T(n)=\Theta (n^{\log _{b}a})=\Theta (n^{2})$. De bovenstaande functie is dus in $\Theta (n^{2})$.

Geval 2

In dit geval is $n^{\log _{b}a}=f(n)$ en dient $f(n)$ gelijk te zijn aan $n^{\log _{b}a}$. Of formeel gezegd, $f(n)=\Theta (n^{\log _{b}a})$.

Als daaraan wordt voldaan, dan volgt daaruit dat $T(n)=\Theta (n^{\log _{b}a}\log n)$.

Voorbeeld

Zij $T(n)=2T\left({\frac {n}{2}}\right)+n$. Dan is $a=2$, $b=2$, $f(n)=n$ en $n^{\log _{b}a}=n$. Zoals te zien is, is $f(n)$ gelijk aan $n^{\log _{b}a}$. Formeel: :$f(n)=\Theta (n^{\log _{b}a})=\Theta (n)$.

Er geldt dus

$T(n)=\Theta \left(n^{\log _{b}a}\log n\right)=\Theta (n\log n)$.

De bovenstaande functie is dus in $\Theta (n\log n)$.

Geval 3

In dit geval is $n^{\log _{b}a}<f(n)$ en dient $f(n)$ polynomiaal groter te zijn dan $n^{\log _{b}a}$. Formeel gezegd:

$f(n)=\Omega \left(n^{\log _{b}a+\epsilon }\right)$ voor een $\epsilon >0$.

De uitdrukking met limieten is dan

${\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\cdot f\!\left({\frac {n}{b}}\right)\leq c\cdot f(n)$ voor een $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)=\Theta (f(n))$.

Voorbeeld

Zij $T(n)=3T\left({\frac {n}{4}}\right)+n\log n$. Dan is $a=3$, $b=4$, $f(n)=n\log n$ en $n^{\log _{b}a}\approx n^{0,79}$. Hier is dus $f(n)$ groter dan $n^{\log _{b}a}$.

Nu moet er nog gecontroleerd worden of de regulariteitsvoorwaarde geldt:

$af\left({\frac {n}{b}}\right)\leq cf(n)$ (voor c<1), het substitueren van de bekende variabelen levert op:

$3({\frac {n}{4}})\log({\frac {n}{4}})\leq c\;n\log n$ (voor c<1). Als er voor $c$ bijvoorbeeld het getal ${\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)=\Theta (f(n))=\Theta (n\log n)$. De bovenstaande functie is dus in $\Theta (n\log n)$.

Beperkingen

Er zijn recurrente betrekkingen van de vorm $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)$ niet polynomiaal groter of kleiner is dan $n^{\log _{b}a}$.

Voorbeeld

Beschouw de formule $T(n)=2T\left({\frac {n}{2}}\right)+n\log n$. Hier is a=2, b=2, $f(n)=n\log n$ en $n^{\log _{b}a}=n$. Het is duidelijk dat $f(n)=\Omega (n)$, dus zitten we in het derde geval. Echter,

${\underset {n\rightarrow \infty }{\lim }}{\frac {n\log n}{n}}={\underset {n\rightarrow \infty }{\lim }}\log n$

Er bestaat geen enkele $\epsilon >0$ zodat $\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).