I denne vejledning lærer du, hvad masterteorem er, og hvordan det bruges til at løse gentagelsesrelationer.
Mastermetoden er en formel til løsning af formens gentagelsesrelationer:
T (n) = aT (n / b) + f (n), hvor, n = størrelse på input a = antal delproblemer i rekursion n / b = størrelse på hvert delproblem. Alle delproblemer antages at have samme størrelse. f (n) = omkostningerne ved det arbejde, der er udført uden for det rekursive opkald, som inkluderer omkostningerne ved at dividere problemet og omkostningerne ved at flette løsningerne Her er a ≧ 1 og b> 1 konstanter, og f (n) er en asymptotisk positiv fungere.
En asymptotisk positiv funktion betyder, at vi har en tilstrækkelig stor værdi af n f(n)> 0.
Master sætningen bruges til at beregne tidskompleksiteten af gentagelsesrelationer (opdele og erobre algoritmer) på en enkel og hurtig måde.
Mestersætning
Hvis a ≧ 1og b> 1er konstanter og f(n)er en asymptotisk positiv funktion, gives tidskompleksiteten af et rekursivt forhold af
T (n) = aT (n / b) + f (n) hvor T (n) har følgende asymptotiske grænser: 1. Hvis f (n) = O (n log b a-ϵ ), så T (n ) = Θ (n log b a ). 2. Hvis f (n) = Θ (n log b a ), så er T (n) = Θ (n log b a * log n). 3. Hvis f (n) = Ω (n log b a + ϵ ), så er T (n) = Θ (f (n)). ϵ> 0 er en konstant.
Hver af ovenstående betingelser kan fortolkes som:
- Hvis omkostningerne ved at løse underproblemerne på hvert niveau stiger med en bestemt faktor, bliver værdien af
f(n)polynomielt mindre end . Således undertrykkes tidskompleksiteten af omkostningerne ved det sidste niveau, dvs.nlogb anlogb a - Hvis omkostningerne ved at løse underproblemet på hvert niveau er næsten lige så vil værdien af
f(n)være . Således vil tidskompleksiteten være gange det samlede antal niveauer, dvs.nlogb af(n)nlogb a * log n - Hvis omkostningerne ved løsning af underproblemer på hvert niveau falder med en bestemt faktor, bliver værdien af
f(n)polynomisk større end . Således undertrykkes tidskompleksiteten af omkostningerne ved .nlogb af(n)
Løst eksempel på masterteorem
T (n) = 3T (n / 2) + n2 Her er a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 dvs. f (n) <n log b a + ϵ , hvor, ϵ er en konstant. Sag 3 antyder her. Således er T (n) = f (n) = Θ (n 2 )
Master Theorem begrænsninger
Master-sætningen kan ikke bruges, hvis:
- T (n) er ikke monoton. for eksempel.
T(n) = sin n f(n)er ikke et polynom. for eksempel.f(n) = 2n- a er ikke konstant. for eksempel.
a = 2n a < 1
