Šioje pamokoje sužinosite, kas yra pagrindinė teorema ir kaip ji naudojama kartojant santykius.
Pagrindinis metodas yra formos pasikartojimo santykių sprendimo formulė:
T (n) = aT (n / b) + f (n), kur, n = įvesties dydis a = rekursijoje esančių subproblemų skaičius n / b = kiekvieno papunkčio dydis. Manoma, kad visi subproblemos yra vienodo dydžio. f (n) = už rekursinio skambučio atlikto darbo kainą, į kurią įeina problemos padalijimo ir sprendimų sujungimo išlaidos. Čia ≧ 1 ir b> 1 yra konstantos, o f (n) yra asimptotiškai teigiamas funkcija.
Asimptotiškai teigiama funkcija reiškia, kad esant pakankamai didelei n reikšmei, mes ją turime f(n)> 0.
Pagrindinė teorema naudojama paprastai ir greitai apskaičiuojant pasikartojimo santykių laiko (sudėtingumo ir užkariavimo algoritmų) sudėtingumą.
Pagrindinė teorema
Jei a ≧ 1ir b> 1yra konstantos ir f(n)yra asimptotiškai teigiama funkcija, tada rekursinio ryšio laiko sudėtingumą nurodo
T (n) = aT (n / b) + f (n) kur, T (n) turi šias asimptotines ribas: 1. Jei f (n) = O (n log b a-ϵ ), tada T (n ) = Θ (n log b a ). 2. Jei f (n) = Θ (n log b a ), tai T (n) = Θ (n log b a * log n). 3. Jei f (n) = Ω (n log b a + ϵ ), tada T (n) = Θ (f (n)). ϵ> 0 yra konstanta.
Kiekvieną iš aukščiau išvardytų sąlygų galima interpretuoti taip:
- Jei kiekvieno lygio subproblemų sprendimo išlaidos padidės tam tikru koeficientu, vertė
f(n)taps polinomiškai mažesnė nei . Taigi laiko sudėtingumą slegia paskutinio lygio kaina, t.nlogb anlogb a - Jei kiekvienos pakopos problemos sprendimo išlaidos yra beveik vienodos, tai
f(n)bus . Taigi laiko sudėtingumas bus kartų didesnis už bendrą lygių skaičių, t.nlogb af(n)nlogb a * log n - Jei kiekvienam lygmeniui būdingų problemų sprendimas kainuos tam tikru koeficientu, jo vertė
f(n)taps polinomiškai didesnė nei . Taigi laiko sudėtingumą slegia išlaidos .nlogb af(n)
Išspręstas pagrindinės teoremos pavyzdys
T (n) = 3T (n / 2) + n2 Čia, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 ty. f (n) <n log b a + ϵ , kur, ϵ yra konstanta. 3 atvejis reiškia čia. Taigi, T (n) = f (n) = Θ (n 2 )
Pagrindinių teoremų apribojimai
Pagrindinės teoremos negalima naudoti, jei:
- T (n) nėra monotoniškas. pvz.
T(n) = sin n f(n)nėra daugianaris. pvz.f(n) = 2n- a nėra konstanta. pvz.
a = 2n a < 1
