Pagrindinė teorema yra įrankis, naudojamas sprendžiant pasikartojimo ryšius, atsirandančius analizuojant „skaldyk ir valdyk“ algoritmus. Pagrindinė teorema pateikia sistemingą būdą, kaip išspręsti formos pasikartojimo ryšius:

T(n) = aT(n/b) + f(n)

1. kur a, b ir f(n) yra teigiamos funkcijos, o n yra problemos dydis. Pagrindinė teorema pateikia sąlygas, kad pasikartojimo sprendimas būtų O(n^k) kai kuriai konstantai k, ir pateikiama formulė k reikšmei nustatyti.
2. Išplėstinė pagrindinės teoremos versija suteikia bendresnę teoremos formą, kuri gali valdyti pasikartojimo ryšius, kurie yra sudėtingesni nei pagrindinė forma. Išplėstinė pagrindinės teoremos versija gali apdoroti pasikartojimus su keliais terminais ir sudėtingesnėmis funkcijomis.
3. Svarbu pažymėti, kad pagrindinė teorema netaikoma visiems pasikartojimo santykiams ir ne visada gali pateikti tikslų tam tikro pasikartojimo sprendimą. Tačiau tai yra naudingas įrankis analizuojant „skaldyk ir valdyk“ algoritmų sudėtingumą laiko atžvilgiu ir yra geras atspirties taškas sprendžiant sudėtingesnius pasikartojimus.

Pagrindinė teorema naudojama algoritmų veikimo laikui (padalyk ir užkariauk) nustatyti asimptotinių žymėjimų požiūriu.
Apsvarstykite problemą, kuri išspręsta naudojant rekursiją.

 function f (input x size n) if (n else divide x into a subproblems of size n/b call f recursively to solve each subproblem Combine the results of all sub-problems>

Aukščiau pateiktas algoritmas padalija problemą į a subproblemas, kurių kiekviena yra n/b dydžio, ir jas rekursyviai išspręskite, kad būtų apskaičiuota problema, o papildomas darbas, atliktas už problemą, yra pateikiamas f(n), t.

Taigi, pagal pagrindinę teoremą aukščiau pateikto algoritmo vykdymo laikas gali būti išreikštas taip:

 T(n) = aT(n/b) + f(n)>

kur n = problemos dydis
a = dalinių uždavinių skaičius rekursijoje ir a>= 1
n/b = kiekvienos subproblemos dydis
f(n) = darbo, atlikto ne per rekursinius skambučius, kaina, pvz., padalijimas į subproblemas ir jų sujungimo, norint gauti sprendimą, kaina.

Ne visi pasikartojimo santykiai gali būti išspręsti naudojant pagrindinę teoremą, ty jei

• T(n) nėra monotoniškas, pvz.: T(n) = sin n
• f(n) nėra daugianomas, pvz.: T(n) = 2T(n/2) + 2ⁿ

Ši teorema yra pažangi pagrindinės teoremos versija, kurią galima naudoti norint nustatyti padalijimo ir užkariavimo algoritmų veikimo laiką, jei pasikartojimas yra tokios formos:

kur n = problemos dydis
a = dalinių uždavinių skaičius rekursijoje ir a>= 1
n/b = kiekvienos subproblemos dydis
b> 1, k>= 0 ir p yra tikrasis skaičius.

Tada

1. jei a> b^k, tada T(n) = θ(n^žurnalas_ba)
2. jei a = b^k, tada
   (a) jei p> -1, tai T(n) = θ(n^žurnalas_bažurnalas^p+1n)
   (b) jei p = -1, tai T(n) = θ(n^žurnalas_baloglogn)
   (c) jei p <-1, tai T(n) = θ(n^žurnalas_ba)
   
3. jeigu k, tada
   (a) jei p>= 0, tai T(n) = θ(n^kžurnalas^pn)
   (b) jei p <0, tai T(n) = θ(n^k)
   

Laiko sudėtingumo analizė –

1 pavyzdys: dvejetainė paieška – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 ir p = 0
b^k= 1. Taigi, a = b^kir p> -1 [atvejis 2.(a)]
T(n) = θ(n^žurnalas_bažurnalas^p+1n)
T(n) = θ(logn) 2 pavyzdys: Sujungti rūšiavimą – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Taigi, a = b^kir p> -1 [atvejis 2.(a)]
T(n) = θ(n^žurnalas_bažurnalas^p+1n)
T(n) = θ(nlogn) 3 pavyzdys: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Taigi, a k ir p = 0 [3 atvejis (a)]
T(n) = θ(n^kžurnalas^pn)
T(n) = θ(n²)

4 pavyzdys: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Taigi, a> b^k[1 atvejis]
T(n) = θ(n^žurnalas_ba)
T(n) = θ(n^{žurnalas₂3})

5 pavyzdys: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Taigi, a = b^k[2 atvejis (a)]
T(n) = θ(n^žurnalas_bažurnalas^p+1n )
T(n) = θ(n^{žurnalas₂2}žurnalas³n)
T(n) = θ(nlog³n)

6 pavyzdys: T(n) = 2ⁿT(n/2) + nⁿ
Šio pasikartojimo negalima išspręsti naudojant aukščiau pateiktą metodą, nes funkcija nėra formos T(n) = aT(n/b) + θ(n^kžurnalas^pn)

GATE praktikos klausimai –

• GATE-CS-2017 (2 rinkinys) | 56 klausimas
• GATE IT 2008 | 42 klausimas
• GATE CS 2009 | 35 klausimas

Štai keletas svarbių dalykų, kuriuos reikia atsiminti, kai kalbama apie pagrindinę teoremą:

1. „Skaldyk ir valdyk“ pasikartojimai: pagrindinė teorema yra specialiai sukurta siekiant išspręsti pasikartojimo ryšius, atsirandančius analizuojant „skaldyk ir užkariauk“ algoritmus.
2. Pasikartojimo forma: Pagrindinė teorema taikoma T(n) = aT(n/b) + f(n) formos pasikartojimo ryšiams, kur a, b ir f(n) yra teigiamos funkcijos, o n yra dydis. problemos.
3. Laiko sudėtingumas: Pagrindinė teorema pateikia sąlygas, kad pasikartojimo sprendimas būtų O(n^k) kai kuriai konstantai k, ir pateikiama formulė k reikšmei nustatyti.
4. Išplėstinė versija: Išplėstinė pagrindinės teoremos versija pateikia bendresnę teoremos formą, kuri gali valdyti pasikartojimo ryšius, kurie yra sudėtingesni nei pagrindinė forma.
5. Apribojimai: Pagrindinė teorema netaikoma visiems pasikartojimo santykiams ir ne visada gali pateikti tikslų tam tikro pasikartojimo sprendimą.
6. Naudingas įrankis: nepaisant savo apribojimų, pagrindinė teorema yra naudingas įrankis analizuojant „skaldyk ir užkariauk“ algoritmų sudėtingumą laiko atžvilgiu ir yra geras atspirties taškas sprendžiant sudėtingesnius pasikartojimus.
7. Papildyta kitais būdais: kai kuriais atvejais pagrindinę teoremą gali tekti papildyti kitais būdais, pvz., pakeitimo metodu arba iteracijos metodu, kad būtų visiškai išspręstas tam tikras pasikartojimo ryšys.