Føreren metode til tilbagefald , ofte kaldet master sætning, beregner de nødvendige ressourcer til at udføre en rekursiv algoritme , såsom køretid på en computer. Føreren metode bruger hvad der er kendt som Big O notation til at beskrive den asymptotiske opførsel af funktioner , hvilket betyder hvor hurtigt de vokser mod deres grænse . Del og hersk

En rekursiv algoritme kan opdeles i sub- problemer , ved hjælp af " del og hersk "-strategi . Hver af disse sub- problemer grene ud fra det oprindelige problem , og kan opfattes som en node. Til master sætning , er disse knudepunkter kaldet n /b , hvor n er størrelsen af ​​det oprindelige problem , og b er det antal stykker , som den er brudt , antages at være af samme størrelse . Fra hver af disse knudepunkter , kan barn noder forgrene sig , som igen kan også behandles én ad gangen med del og hersk -strategi.
Master Theorem

føreren sætning virker for rekursive algoritmer T ( n ) , hvor T ( n ) = aT (n /b ) + f (n ) , og T ( 1 ) = C , således at der er en startværdi , hvorfra man kan generere rekursion . Et eksempel er T ( n ) = 2T ( n /4 ) + n ^ 2 . Føreren sætning derefter kategoriserer den algoritme i en kategori med andre algoritmer , der tager den samme mængde arbejde .

Der ikke omfattes

Føreren teorem kan ikke være anvendes, hvis T ( n) er en monoton , såsom synd n. . En sådan funktion ikke oplever vækst, hvilket er hvorfor det kaldes en monoton . f (n ) skal være et polynomium , sådan 2x ^ 3 + 3x + 4 , i modsætning til funktioner som 2 ^ n . b skal være mindst 2, og en skal være på mindst 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)

det fortæller os, at dette rekursive algoritme hører til den type n ^ 3 , og vil have samme run tid som andre algoritmer i denne kategori.
< br >