Šajā apmācībā jūs uzzināsiet, kas ir galvenā teorēma un kā tā tiek izmantota atkārtošanās attiecību risināšanai.
Galvenā metode ir forma formas atkārtošanās attiecību risināšanai:
T (n) = aT (n / b) + f (n), kur n = ievades lielums a = apakšproblēmu skaits rekursijā n / b = katras apakšproblēmas lielums. Tiek pieņemts, ka visām apakšproblēmām ir vienāds izmērs. f (n) = ārpus rekurzīvā zvana veiktā darba izmaksas, kas ietver problēmas dalīšanas izmaksas un risinājumu apvienošanas izmaksas Šeit a a 1 un b> 1 ir konstantes, un f (n) ir asimptotiski pozitīvs funkciju.
Asimptotiski pozitīva funkcija nozīmē, ka mums ir pietiekami liela n vērtība f(n)> 0.
Galveno teorēmu izmanto, lai vienkāršotā un ātrā veidā aprēķinātu atkārtošanās attiecību laika sarežģītību (dalīšanas un iekarošanas algoritmus).
Maģistra teorēma
Ja a ≧ 1un b> 1ir konstantes un f(n)ir asimptotiski pozitīva funkcija, tad rekursīvās attiecības laika sarežģītību nosaka
T (n) = aT (n / b) + f (n) kur, T (n) ir šādas asimptotiskas robežas: 1. Ja f (n) = O (n log b a-ϵ ), tad T (n ) = Θ (n log b a ). 2. Ja f (n) = Θ (n log b a ), tad T (n) = Θ (n log b a * log n). 3. Ja f (n) = Ω (n log b a + ϵ ), tad T (n) = Θ (f (n)). ϵ> 0 ir konstante.
Katru no iepriekš minētajiem nosacījumiem var interpretēt kā:
- Ja apakšu problēmu risināšanas izmaksas katrā līmenī palielināsies par noteiktu faktoru, vērtība
f(n)kļūs polinomiski mazāka nekā . Tādējādi laika sarežģītību nomāc pēdējā līmeņa izmaksas, ti.nlogb anlogb a - Ja apakšproblēmas risināšanas izmaksas katrā līmenī ir gandrīz vienādas, tad vērtība
f(n)būs . Tādējādi laika sarežģītība reizinās ar kopējo līmeņu skaitu, ti.nlogb af(n)nlogb a * log n - Ja apakšproblēmu risināšanas izmaksas katrā līmenī samazināsies par noteiktu faktoru, vērtība
f(n)kļūs polinomiski lielāka par . Tādējādi laika sarežģītību nomāc izmaksas .nlogb af(n)
Atrisināts Meistaru teorēmas piemērs
T (n) = 3T (n / 2) + n2 Šeit a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1,58 <2 ti. f (n) <n log b a + ϵ , kur, ϵ ir konstante. Šeit ir norādīts 3. gadījums. Tādējādi T (n) = f (n) = Θ (n 2 )
Galvenās teorēmas ierobežojumi
Galveno teorēmu nevar izmantot, ja:
- T (n) nav monotons. piem.
T(n) = sin n f(n)nav polinoms. piem.f(n) = 2n- a nav konstante. piem.
a = 2n a < 1
