I denne veiledningen vil du lære hva masterteorem er og hvordan det brukes til å løse gjentakelsesrelasjoner.
Mastermetoden er en formel for å løse gjentakelsesrelasjoner av skjemaet:
T (n) = aT (n / b) + f (n), der, n = inngangsstørrelse a = antall delproblemer i rekursjonen n / b = størrelse på hvert delproblem. Alle delproblemer antas å ha samme størrelse. f (n) = kostnad for arbeidet som er gjort utenfor den rekursive samtalen, som inkluderer kostnadene ved å dele problemet og kostnadene ved å slå sammen løsningene. Her er a ≧ 1 og b> 1 konstanter, og f (n) er en asymptotisk positiv funksjon.
En asymptotisk positiv funksjon betyr at for en tilstrekkelig stor verdi av n har vi f(n)> 0.
Mestersetningen brukes til å beregne tidskompleksiteten til gjentakelsesrelasjoner (dele og erobre algoritmer) på en enkel og rask måte.
Mestersetning
Hvis a ≧ 1og b> 1er konstanter og f(n)er en asymptotisk positiv funksjon, blir tidskompleksiteten til et rekursivt forhold gitt av
T (n) = aT (n / b) + f (n) hvor, T (n) har følgende asymptotiske grenser: 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 av de ovennevnte forholdene kan tolkes som:
- Hvis kostnaden for å løse underproblemene på hvert nivå øker med en viss faktor, vil verdien av
f(n)bli polynomielt mindre enn . Dermed undertrykkes tidskompleksiteten av kostnaden for det siste nivået, dvs.nlogb anlogb a - Hvis kostnadene for å løse underproblemet på hvert nivå er nesten like, vil verdien av
f(n)være . Dermed vil tidskompleksiteten være ganger det totale antall nivåer, dvs.nlogb af(n)nlogb a * log n - Hvis kostnadene ved å løse underproblemene på hvert nivå synker med en viss faktor, blir verdien av
f(n)polynomisk større enn . Dermed undertrykkes tidskompleksiteten av kostnaden for .nlogb af(n)
Løst eksempel på masterteori
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 + ϵ , der, ϵ er en konstant. Sak 3 antyder her. Dermed er T (n) = f (n) = Θ (n 2 )
Master Theorem Limitations
Masterteoremet kan ikke brukes hvis:
- T (n) er ikke monoton. f.eks.
T(n) = sin n f(n)er ikke et polynom. f.eks.f(n) = 2n- a er ikke en konstant. f.eks.
a = 2n a < 1
