The master metode for tilbakefall , ofte kalt mesteren teorem , beregner de nødvendige ressursene for å utføre en rekursiv algoritme , som for eksempel kjøretid på en datamaskin . Master metoden bruker det som er kjent som Big O notasjon for å beskrive den asymptotiske oppførselen til funksjoner , som betyr hvor fort de vokser mot grensen sin . Splitt og hersk

En rekursiv algoritme kan bli brutt ned i sub- problemer , ved hjelp av " splitt og hersk "-strategi . Hver av disse sub- problemer grener av fra det opprinnelige problemet , og kan betraktes som en node . For master teorem, blir disse nodene N /B , hvor N er størrelsen av det opprinnelige problem , og b er antall biter inn i hvilken det er brutt , som antas å være like store. Fra hver av disse nodene , kan barnet noder grenen av , som i sin tur kan også tas opp en om gangen med splitt og hersk strategi.
Master Theorem

master teoremet fungerer for rekursive algoritmer T (n), hvor T ( n) = aT ( i /b ) + f ( n) og T ( 1) = c, slik at det er en startverdi for å generere rekursjon . Et eksempel er T ( n) = 2T (n /4) + n ^ 2 . Master teorem kategoriserer da algoritmen inn i en kategori med andre algoritmer som tar samme mengde arbeid.

Cases ikke dekkes

Mesteren teoremet kan ikke være benyttes dersom T ( n) er en monoton , slik som sin N . En slik funksjon ikke opplever vekst , og det er derfor det kalles en monoton . f (n ) må være et polynom , slik 2x ^ 3 + 3x + 4, i motsetning til funksjoner som 2 ^ n . b må være minst to , og en må være minst 1 , og c skal være positiv.
Eksempel

T ( n) = 8T (n /2 ) + 1000N ^ 2

T (n ) = theta ( n ^ ( log_base_b a) )

a = 8

b = 2

T (n ) = theta ( n ^ 3 )
p Dette forteller oss at dette rekursiv algoritme tilhører den type n ^ 3 , og vil ha samme kjøretid som andre algoritmer i den kategorien .