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\ge 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)=\mathrm{\Theta }(n^{{\log }_{b}a})$;
• Geval 2: als $n^{{\log }_{b}a}=f(n)$, dan $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a}\log n)$;
• Geval 3: als $n^{{\log }_{b}a}<f(n)$, dan $T(n)=\mathrm{\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-ϵ})$ voor een $ϵ>0$. Dit kan men ook nog uitdrukken als

$\underset{n\to \mathrm{\infty }}{\lim }\frac{n^{{\log }_{b}a}}{f(n)}=\underset{n\to \mathrm{\infty }}{\lim }{n}^{ϵ}$

Voor een zekere $ϵ>0$.

Als daaraan wordt voldaan, dan volgt dat $T(n)=\mathrm{\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 $ϵ=1$ te nemen.

Er geldt dus $T(n)=\mathrm{\Theta }(n^{{\log }_{b}a})=\mathrm{\Theta }(n^2)$. De bovenstaande functie is dus in $\mathrm{\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)=\mathrm{\Theta }(n^{{\log }_{b}a})$.

Als daaraan wordt voldaan, dan volgt daaruit dat $T(n)=\mathrm{\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)=\mathrm{\Theta }(n^{{\log }_{b}a})=\mathrm{\Theta }(n)$.

Er geldt dus

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

De bovenstaande functie is dus in $\mathrm{\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)=\mathrm{\Omega }\left(n^{{\log }_{b}a+ϵ}\right)$ voor een $ϵ>0$.

De uitdrukking met limieten is dan

$\underset{n\to \mathrm{\infty }}{\lim }\frac{f(n)}{n^{{\log }_{b}a}}=\underset{n\to \mathrm{\infty }}{\lim }{n}^{ϵ}$

Voor geval 3 geldt daarnaast een tweede voorwaarde, de regulariteitsvoorwaarde. Er dient te gelden dat $a\cdot f\left(\frac{n}{b}\right)\le 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)=\mathrm{\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)\le cf(n)$ (voor c<1), het substitueren van de bekende variabelen levert op:

$3(\frac{n}{4})\log (\frac{n}{4})\le cn\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)=\mathrm{\Theta }(f(n))=\mathrm{\Theta }(n\log n)$. De bovenstaande functie is dus in $\mathrm{\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)=\mathrm{\Omega }(n)$, dus zitten we in het derde geval. Echter,

$\underset{n\to \mathrm{\infty }}{\lim }\frac{n\log n}{n}=\underset{n\to \mathrm{\infty }}{\lim }\log n$

Er bestaat geen enkele $ϵ>0$ zodat $\log n=n^{ϵ}$, en dus kan de master theorem niet worden toegepast.