V tej vadnici boste izvedeli, kaj je glavni izrek in kako se uporablja za reševanje ponovitvenih razmerij.
Glavna metoda je formula za reševanje ponovitvenih razmerij oblike:
T (n) = aT (n / b) + f (n), kjer je n = velikost vnosa a = število podproblemov v rekurziji n / b = velikost vsakega podproblema. Vsi podproblemi naj bi imeli enako velikost. f (n) = stroški dela, opravljenega zunaj rekurzivnega klica, ki vključuje stroške delitve problema in stroške združevanja rešitev. Tu sta a ≧ 1 in b> 1 konstanti, f (n) pa asimptotično pozitiven funkcijo.
Asimptotično pozitivna funkcija pomeni, da imamo za dovolj veliko vrednost n f(n)> 0.
Glavni izrek se na preprost in hiter način uporablja za izračun časovne zapletenosti relacij ponovitve (algoritmi deli in vladaj).
Mojster izrek
Če a ≧ 1in b> 1sta konstanti in f(n)je asimptotično pozitivna funkcija, potem je časovna zapletenost rekurzivnega razmerja podana z
T (n) = aT (n / b) + f (n) pri čemer ima T (n) naslednje asimptotske meje: 1. Če je f (n) = O (n log b a-ϵ ), potem T (n ) = Θ (n log b a ). 2. Če je f (n) = Θ (n log b a ), potem je T (n) = Θ (n log b a * log n). 3. Če je f (n) = Ω (n log b a + ϵ ), potem je T (n) = Θ (f (n)). ϵ> 0 je konstanta.
Vsakega od zgornjih pogojev si lahko razlagamo kot:
- Če se stroški reševanja podproblemov na vsaki ravni povečajo za določen dejavnik, bo vrednost
f(n)polinomsko manjša od . Tako časovno zapletenost zatirajo stroški zadnje stopnje, tj.nlogb anlogb a - Če je strošek reševanja sub-problem na vsaki ravni skoraj enaka, potem je vrednost
f(n)bo . Tako bo časovna zapletenost pomnožena s skupnim številom ravni, tj.nlogb af(n)nlogb a * log n - Če se stroški reševanja podproblemov na posamezni ravni zmanjšajo za določen faktor, bo vrednost
f(n)polinomsko večja od . Tako časovno zapletenost zatirajo stroški .nlogb af(n)
Rešeni primer glavnega teorema
T (n) = 3T (n / 2) + n2 Tu 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 + ϵ , kjer je ϵ konstanta. Primer 3 tukaj nakazuje. Tako je T (n) = f (n) = Θ (n 2 )
Omejitve glavnega teorema
Glavnega izreka ni mogoče uporabiti, če:
- T (n) ni monoton. npr.
T(n) = sin n f(n)ni polinom. npr.f(n) = 2n- a ni stalnica. npr.
a = 2n a < 1
