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 ${\displaystyle n}$ het probleem wordt opgedeeld in ${\displaystyle a}$ deelproblemen ter grootte van ${\displaystyle n/b}$, waarin ${\displaystyle a\geq 1}$ en ${\displaystyle b>1}$, heeft de looptijd de vorm

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

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

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

Geval 1

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

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

Voor een zekere ${\displaystyle \epsilon >0}$.

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

Voorbeeld

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

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

Geval 2

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

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

Voorbeeld

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

Er geldt dus

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

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

Geval 3

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

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

De uitdrukking met limieten is dan

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

Voorbeeld

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

Nu moet er nog gecontroleerd worden of de regulariteitsvoorwaarde geldt:

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

${\displaystyle 3({\frac {n}{4}})\log({\frac {n}{4}})\leq c\;n\log n}$ (voor c<1). Als er voor ${\displaystyle c}$ bijvoorbeeld het getal ${\displaystyle {\frac {3}{4}}}$ wordt genomen, dan is er dus aan de regulariteitsvoorwaarde voldaan.

Omdat er aan beide voorwaarden is voldaan, geldt er dus ${\displaystyle T(n)=\Theta (f(n))=\Theta (n\log n)}$. De bovenstaande functie is dus in ${\displaystyle \Theta (n\log n)}$.

Beperkingen

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

Voorbeeld

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

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

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