V tomto výučbe sa dozviete, čo je hlavná veta a ako sa používa na riešenie vzťahov opakovania.
Hlavná metóda je vzorec na riešenie rekurentných vzťahov formulára:
T (n) = aT (n / b) + f (n), kde, n = veľkosť vstupu a = počet čiastkových problémov v rekurzii n / b = veľkosť každého čiastkového problému. Predpokladá sa, že všetky podproblémy majú rovnakú veľkosť. f (n) = náklady na prácu vykonanú mimo rekurzívneho volania, ktoré zahŕňajú náklady na rozdelenie problému a náklady na zlúčenie riešení. Tu sú a ≧ 1 a b> 1 konštanty a f (n) je asymptoticky pozitívny funkcia.
Asymptoticky pozitívna funkcia znamená, že pre dostatočne veľkú hodnotu n máme f(n)> 0.
Hlavná veta sa používa na jednoduchý a rýchly výpočet časovej zložitosti vzťahov rekurencie (algoritmy rozdeľuj a panuj).
Hlavná veta
Ak a ≧ 1a b> 1sú konštanty a f(n)je asymptoticky pozitívna funkcia, potom je časová zložitosť rekurzívneho vzťahu daná vzťahom
T (n) = aT (n / b) + f (n), kde T (n) má nasledujúce asymptotické hranice: 1. Ak f (n) = O (n log b a-ϵ ), potom T (n) ) = Θ (n log b a ). 2. Ak f (n) = Θ (n log b a ), potom T (n) = Θ (n log b a * log n). 3. Ak f (n) = Ω (n log b a + ϵ ), potom T (n) = Θ (f (n)). ϵ> 0 je konštanta.
Každú z vyššie uvedených podmienok je možné interpretovať ako:
- Ak sa náklady na riešenie čiastkových problémov na každej úrovni zvýšia o určitý faktor, hodnota
f(n)sa stane polynomiálne menšou ako . Časová zložitosť je teda utláčaná nákladmi na poslednú úroveň, tj.nlogb anlogb a - V prípade, že náklady na riešenie čiastkového problému v každej úrovni je takmer zhodné, potom by sa hodnota
f(n)bude . Časová zložitosť bude teda násobkom celkového počtu úrovní, tj.nlogb af(n)nlogb a * log n - Ak náklady na riešenie podproblémov na každej úrovni poklesnú o určitý faktor, hodnota
f(n)bude polynomiálne vyššia ako . Preto je časová zložitosť utláčaná nákladmi na .nlogb af(n)
Vyriešený príklad hlavnej vety
T (n) = 3T (n / 2) + n2 Tu 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 + ϵ , kde, ϵ je konštanta. Prípad 3 tu naznačuje. T (T) = f (n) = Θ (n 2 )
Obmedzenia hlavnej vety
Hlavnú vetu nemožno použiť, ak:
- T (n) nie je monotónny. napr.
T(n) = sin n f(n)nie je polynóm. napr.f(n) = 2n- a nie je konštanta. napr.
a = 2n a < 1
