Master Metode for Regelmessighet

Hovedfremgangsmåten for tilbakefall, ofte kalt master teorem, beregner de nødvendige for å utføre en rekursiv algoritme, slik som kjøring på en datamaskin ressurser. Hoved 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 sin grense.

Splitt og hersk

En rekursiv algoritme kan bli brutt ned i sub-problemer, ved hjelp av "splitt og hersk" strategi. Hver av disse under problemer grener av fra det opprinnelige problemet og kan betraktes som en node. For hoved teorem, blir disse nodene kalles n / f, hvor n er størrelsen av det opprinnelige problem, og b er antall brikker som den er brutt, antas å være like store. Fra hver av disse nodene, barn noder kan avgreining, som i sin tur kan også rettes en av gangen med splitt og hersk-strategi.

Master Theorem

Hoved teoremet som fungerer for rekursive algoritmer T (n), hvor T (n) = aT (n / 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. Hoved teorem kategoriserer deretter algoritmen i en kategori med andre algoritmer som tar den samme mengden arbeid.

Saker som ikke dekkes

Hoved teoremet kan ikke brukes hvis 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 2, og en må være minst 1, og c må 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)

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.