Galvenā teorēma ir rīks, ko izmanto, lai atrisinātu atkārtošanās attiecības, kas rodas dalīšanas un valdīšanas algoritmu analīzē. Galvenā teorēma sniedz sistemātisku veidu, kā atrisināt šādas formas atkārtošanās attiecības:

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

1. kur a, b un f(n) ir pozitīvas funkcijas un n ir problēmas lielums. Galvenā teorēma sniedz nosacījumus, lai atkārtojuma atrisinājums būtu O(n^k) formā kādai konstantei k, un tā dod formulu k vērtības noteikšanai.
2. Galvenās teorēmas uzlabotā versija nodrošina vispārīgāku teorēmas formu, kas var apstrādāt atkārtošanās attiecības, kas ir sarežģītākas nekā pamata forma. Galvenās teorēmas uzlabotā versija var apstrādāt atkārtojumus ar vairākiem terminiem un sarežģītākām funkcijām.
3. Ir svarīgi atzīmēt, ka galvenā teorēma nav piemērojama visām atkārtošanās attiecībām, un tā ne vienmēr var sniegt precīzu risinājumu konkrētam atkārtojumam. Tomēr tas ir noderīgs rīks, lai analizētu sadali un valdi algoritmu laika sarežģītību, un tas ir labs sākumpunkts sarežģītāku atkārtojumu risināšanai.

Galvenā teorēma tiek izmantota, lai noteiktu algoritmu darbības laiku (dali un iekaro algoritmu) asimptotisko apzīmējumu izteiksmē.
Apsveriet problēmu, kas tiek atrisināta, izmantojot rekursiju.

 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>

Iepriekš minētais algoritms sadala problēmu a apakšproblēmas, katra ar lielumu n/b, un atrisiniet tās rekursīvi, lai aprēķinātu problēmu, un uzdevumam papildu darbs tiek dots f(n), t.i., laiks apakšproblēmu izveidošanai un to rezultātu apvienošanai iepriekš minētajā procedūrā.

Tātad saskaņā ar galveno teorēmu iepriekšminētā algoritma izpildes laiku var izteikt šādi:

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

kur n = problēmas lielums
a = apakšproblēmu skaits rekursijā un a>= 1
n/b = katras apakšproblēmas lielums
f(n) = izmaksas par darbu, kas veikts ārpus rekursīviem izsaukumiem, piemēram, sadalīšana apakšproblēmās un to apvienošanas izmaksas, lai iegūtu risinājumu.

Ne visas atkārtošanās attiecības var atrisināt, izmantojot galveno teorēmu, t.i., ja

• T(n) nav monotons, piemēram: T(n) = sin n
• f(n) nav polinoms, piemēram: T(n) = 2T(n/2) + 2ⁿ

Šī teorēma ir galvenās teorēmas uzlabota versija, ko var izmantot, lai noteiktu sadalīšanas un iekarošanas algoritmu darbības laiku, ja atkārtošanās ir šādā formā:

kur n = problēmas lielums
a = apakšproblēmu skaits rekursijā un a>= 1
n/b = katras apakšproblēmas lielums
b> 1, k>= 0 un p ir reāls skaitlis.

Tad

1. ja a> b^k, tad T(n) = θ(n^žurnāls_ba)
2. ja a = b^k, tad
   (a) ja p> -1, tad T(n) = θ(n^žurnāls_bažurnāls^p+1n)
   (b) ja p = -1, tad T(n) = θ(n^žurnāls_baloglogn)
   (c) ja p <-1, tad T(n) = θ(n^žurnāls_ba)
   
3. ja k, tad
   (a) ja p>= 0, tad T(n) = θ(n^kžurnāls^lppn)
   (b) ja p <0, tad T(n) = θ(n^k)
   

Laika sarežģītības analīze -

1. piemērs: binārā meklēšana — T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 un p = 0
b^k= 1. Tātad, a = b^kun p> -1 [2. gadījums (a)]
T(n) = θ(n^žurnāls_bažurnāls^p+1n)
T(n) = θ(logn) 2. piemērs: sapludināšanas kārtošana — T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Tātad, a = b^kun p> -1 [2. gadījums (a)]
T(n) = θ(n^žurnāls_bažurnāls^p+1n)
T(n) = θ(nlogn) 3. piemērs: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Tātad, a k un p = 0 [3. gadījums (a)]
T(n) = θ(n^kžurnāls^lppn)
T(n) = θ(n²)

4. piemērs: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Tātad, a> b^k[1. gadījums]
T(n) = θ(n^žurnāls_ba)
T(n) = θ(n^{žurnāls₂3})

5. piemērs: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Tātad, a = b^k[Lieta 2.(a)]
T(n) = θ(n^žurnāls_bažurnāls^p+1n )
T(n) = θ(n^{žurnāls₂2}žurnāls³n)
T(n) = θ(nlog³n)

6. piemērs: T(n) = 2ⁿT(n/2) + nⁿ
Šo atkārtošanos nevar atrisināt, izmantojot iepriekš minēto metodi, jo funkcijai nav formas T(n) = aT(n/b) + θ(n^kžurnāls^lppn)

VĀRTU prakses jautājumi –

• GATE-CS-2017 (2. komplekts) | 56. jautājums
• GATE IT 2008 | 42. jautājums
• GATE CS 2009 | 35. jautājums

Šeit ir daži svarīgi punkti, kas jāpatur prātā saistībā ar galveno teorēmu:

1. “Skaldi un valdi” atkārtojumi: galvenā teorēma ir īpaši izstrādāta, lai atrisinātu atkārtošanās attiecības, kas rodas dalīšanas un valdīšanas algoritmu analīzē.
2. Atkārtošanās forma: Galvenā teorēma attiecas uz atkārtošanās relācijām formā T(n) = aT(n/b) + f(n), kur a, b un f(n) ir pozitīvas funkcijas un n ir lielums. no problēmas.
3. Laika sarežģītība: Galvenā teorēma nodrošina nosacījumus, lai atkārtošanās atrisinājums būtu O(n^k) formā kādai konstantei k, un tā dod formulu k vērtības noteikšanai.
4. Uzlabotā versija: Galvenās teorēmas uzlabotā versija nodrošina vispārīgāku teorēmas formu, kas spēj apstrādāt atkārtošanās attiecības, kas ir sarežģītākas par pamatformu.
5. Ierobežojumi: Galvenā teorēma nav piemērojama visām atkārtošanās attiecībām, un tā ne vienmēr var nodrošināt precīzu konkrēta atkārtojuma risinājumu.
6. Noderīgs rīks: neskatoties uz ierobežojumiem, galvenā teorēma ir noderīgs rīks, lai analizētu sadali un valdi algoritmu laika sarežģītību, un tas nodrošina labu sākumpunktu sarežģītāku atkārtojumu risināšanai.
7. Papildināts ar citiem paņēmieniem: Dažos gadījumos galvenā teorēma var būt jāpapildina ar citiem paņēmieniem, piemēram, aizstāšanas metodi vai iterācijas metodi, lai pilnībā atrisinātu doto atkārtošanās sakarību.