U ovom ćete tutorijalu naučiti što je glavni teorem i kako se koristi za rješavanje relacija ponavljanja.
Glavna metoda je formula za rješavanje relacija ponavljanja oblika:
T (n) = aT (n / b) + f (n), gdje je, n = veličina ulaza a = broj potproblema u rekurziji n / b = veličina svakog potproblema. Pretpostavlja se da svi podproblemi imaju istu veličinu. f (n) = trošak posla obavljenog izvan rekurzivnog poziva, koji uključuje cijenu podjele problema i troškove spajanja rješenja Ovdje su a ≧ 1 i b> 1 konstante, a f (n) je asimptotički pozitivan funkcija.
Asimptotički pozitivna funkcija znači da za dovoljno veliku vrijednost n imamo f(n)> 0.
Glavni se teorem koristi na jednostavan i brz način za izračunavanje vremenske složenosti relacija ponavljanja (algoritmi podijeli i osvoji).
Master teorem
Ako su a ≧ 1i b> 1konstante i f(n)je asimptotički pozitivna funkcija, tada je vremenska složenost rekurzivne relacije dana
T (n) = aT (n / b) + f (n) gdje T (n) ima sljedeće asimptotske granice: 1. Ako je f (n) = O (n log b a-ϵ ), tada je T (n ) = Θ (n log b a ). 2. Ako je f (n) = Θ (n log b a ), tada je T (n) = Θ (n log b a * log n). 3. Ako je f (n) = Ω (n log b a + ϵ ), tada je T (n) = Θ (f (n)). ϵ> 0 je konstanta.
Svaki od gore navedenih uvjeta može se protumačiti kao:
- Ako se troškovi rješavanja potproblema na svakoj razini povećaju za određeni čimbenik, vrijednost x
f(n)postat će polinomno manja od . Dakle, vremensku složenost potiskuje trošak posljednje razine, tj.nlogb anlogb a - Ako su troškovi rješavanja potproblema na svakoj razini gotovo jednaki, tada će vrijednost
f(n)biti . Dakle, vremenska složenost bit će pomnožena s ukupnim brojem razina, tj.nlogb af(n)nlogb a * log n - Ako se troškovi rješavanja potproblema na svakoj razini smanje za određeni faktor, vrijednost
f(n)će postati polinomski veća od . Dakle, vremensku složenost potlačuju troškovi .nlogb af(n)
Riješeni primjer glavnog teorema
T (n) = 3T (n / 2) + n2 Ovdje je a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 tj. f (n) <n log b a + ϵ , gdje je ϵ konstanta. Slučaj 3 ovdje implicira. Dakle, T (n) = f (n) = Θ (n 2 )
Ograničenja glavnog teorema
Glavni teorem ne može se koristiti ako:
- T (n) nije monoton. npr.
T(n) = sin n f(n)nije polinom. npr.f(n) = 2n- a nije konstanta. npr.
a = 2n a < 1
