Master-theorem

Uit Wikipedia, de vrije encyclopedie
(Doorverwezen vanaf Master theorem)
Ga naar: navigatie, zoeken

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[bewerken]

Als voor het berekenen van een probleem van grootte n het probleem wordt opgedeeld in a deelproblemen ter grootte van n/b, waarin a,b\ge 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),
  • Geval 2: als n^{\log_b a} = f(n),
  • Geval 3: als n^{\log_b a} < f(n).

Geval 1[bewerken]

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_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[bewerken]

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[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}. 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[bewerken]

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_ba}} = \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) \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) = \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.