Master theorem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De master theorem biedt een methode (master method) die het bepalen van de looptijd van recurrente betrekkingen in de algoritmiek gemakkelijk maakt. De master theorem kan echter niet de complexiteit van alle recurrente betrekkingen bepalen.

Theorie[bewerken]

Men kan recurrente betrekkingen als volgt weergeven: T(n) = a T\!\left(\frac{n}{b}\right) + f(n) (waar a>1 en constant en b>1 en constant). Deze formule beschrijft de looptijd van een algoritme, waarin een probleem van grootte n in a deelproblemen wordt gedeeld en de deelproblemen een grootte van \frac{n}{b} hebben. Elke aanroep van de formule heeft een looptijd van f(n).

Men onderscheidt drie gevallen in de master theorem. Welk geval van toepassing is, is afhankelijk van de verhouding tussen f(n) en n^{\log_{b} a}. Als n^{\log_{b} a} > f(n), dan is geval 1 van toepassing; als n^{\log_b a} = f(n) dan is geval 2 van toepassing en als n^{\log_{b} a} < f(n) dan is geval 3 van toepassing.

Geval 1: n^{\log_{b} a} > f(n)[bewerken]

Bij geval 1 dient f(n) polynomiaal kleiner te zijn dan n^{\log_{b} a}. Of 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_ba}}{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[bewerken]

Zij T(n) = 9 T(\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 f(n) kleiner dan n^{\log_{b} a}. 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: n^{\log_b a} = f(n)[bewerken]

Bij geval 2 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[bewerken]

Zij T(n) = 2 T\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}, of 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: n^{\log_{b} a} < f(n)[bewerken]

Bij geval 3 dient f(n) polynomiaal groter te zijn dan n^{\log_{b} a}. Of 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_ba}} = \underset{n\rightarrow\infty}{\lim} n^\epsilon

Voor geval 3 geldt daarnaast een tweede voorwaarde, de regulariteitsvoorwaarde. Er dient te gelden dat a f \left(\frac{n}{b}\right) \le cf(n) voor een c<1. Als deze niet geldt, dan kan de looptijd niet met de master theorem bepaald worden.

Als er aan deze voorwaarden wordt voldaan, dan volgt daaruit dat T(n) = \Theta(f(n)).

Voorbeeld[bewerken]

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:

a f \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 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[bewerken]

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_ba}.

Voorbeeld[bewerken]

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_ba} = 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 logartimes bedoeld met grondgetal 2 (lb volgens ISO 31-11).