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 het probleem wordt opgedeeld in deelproblemen ter grootte van , waarin , heeft de looptijd de vorm

.

Daarin is 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 en .

  • Geval 1: als ,
  • Geval 2: als ,
  • Geval 3: als .

Geval 1[bewerken]

In dit geval is , dus dient polynomiaal kleiner te zijn dan . Formeel gezegd: voor een . Dit kan men ook nog uitdrukken als

Voor een zekere .

Als daaraan wordt voldaan, dan volgt dat

Voorbeeld[bewerken]

Zij . Dan is , , en . Zoals duidelijk te zien is, is kleiner dan . In de formele voorwaarde valt dit goed te zien door te nemen.

Er geldt dus . De bovenstaande functie is dus in .

Geval 2[bewerken]

In dit geval is en dient gelijk te zijn aan . Of formeel gezegd, .

Als daaraan wordt voldaan, dan volgt daaruit dat .

Voorbeeld[bewerken]

Zij . Dan is , , en . Zoals te zien is, is gelijk aan . Formeel: :.

Er geldt dus

.

De bovenstaande functie is dus in .

Geval 3[bewerken]

In dit geval is en dient polynomiaal groter te zijn dan . Formeel gezegd:

voor een .

De uitdrukking met limieten is dan

Voor geval 3 geldt daarnaast een tweede voorwaarde, de regulariteitsvoorwaarde. Er dient te gelden dat voor een . Als dit niet geldt, kan de looptijd niet met het master-theorem bepaald worden.

Als er aan deze voorwaarden wordt voldaan, volgt daaruit dat .

Voorbeeld[bewerken]

Zij . Dan is , , en . Hier is dus groter dan .

Nu moet er nog gecontroleerd worden of de regulariteitsvoorwaarde geldt:

(voor c<1), het substitueren van de bekende variabelen levert op:
(voor c<1). Als er voor bijvoorbeeld het getal wordt genomen, dan is er dus aan de regulariteitsvoorwaarde voldaan.

Omdat er aan beide voorwaarden is voldaan, geldt er dus . De bovenstaande functie is dus in .

Beperkingen[bewerken]

Er zijn recurrente betrekkingen van de vorm waarvan de looptijd niet met deze methode bepaald kan worden, omdat niet aan de regulariteitsvoorwaarde wordt voldaan of omdat niet polynomiaal groter of kleiner is dan .

Voorbeeld[bewerken]

Beschouw de formule . Hier is a=2, b=2, en . Het is duidelijk dat , dus zitten we in het derde geval. Echter,

Er bestaat geen enkele zodat , en dus kan de master theorem niet worden toegepast.