Master Theorem on työkalu, jolla ratkaistaan ​​toistuvuussuhteita, jotka syntyvät hajoa ja hallitse -algoritmien analysoinnissa. Päälause tarjoaa systemaattisen tavan ratkaista toistuvuussuhteet muodossa:

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

1. missä a, b ja f(n) ovat positiivisia funktioita ja n on ongelman koko. Päälause tarjoaa ehdot sille, että toistumisen ratkaisu on O(n^k):n muodossa jollekin vakiolle k, ja se antaa kaavan k:n arvon määrittämiseksi.
2. Päälauseen edistynyt versio tarjoaa yleisemmän muodon lauseesta, joka pystyy käsittelemään perusmuotoa monimutkaisempia toistuvuussuhteita. Master Theoreemin edistynyt versio pystyy käsittelemään toistuvia termejä ja monimutkaisempia toimintoja.
3. On tärkeää huomata, että Master Lause ei sovellu kaikkiin toistuvuussuhteisiin, eikä se välttämättä aina tarjoa tarkkaa ratkaisua tiettyyn toistumiseen. Se on kuitenkin hyödyllinen työkalu hajota ja hallitse -algoritmien aikamonimutkaisuuden analysointiin ja se tarjoaa hyvän lähtökohdan monimutkaisempien toistojen ratkaisemiseen.

Päälausetta käytetään määrittämään algoritmien (jako ja hallitse -algoritmien) ajoaika asymptoottisten merkintöjen avulla.
Harkitse ongelmaa, joka ratkaistaan ​​rekursiolla.

 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>

Yllä oleva algoritmi jakaa ongelman kahteen osaan a aliongelmat, kukin kooltaan n/b ja ratkaista ne rekursiivisesti laskeaksesi ongelman ja tehtävälle tehtävä ylimääräinen työ on f(n), eli aika aliongelmien luomiseen ja niiden tulosten yhdistämiseen yllä olevassa menettelyssä.

Joten päälauseen mukaan yllä olevan algoritmin suoritusaika voidaan ilmaista seuraavasti:

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

missä n = ongelman koko
a = alitehtävien määrä rekursiossa ja a>= 1
n/b = kunkin aliongelman koko
f(n) = rekursiivisten kutsujen ulkopuolella tehdyn työn hinta, kuten aliongelmiin jakaminen ja niiden yhdistämisen hinta ratkaisun saamiseksi.

Kaikkia toistuvuussuhteita ei voida ratkaista käyttämällä päälausetta eli jos

• T(n) ei ole monotoninen, esim.: T(n) = sin n
• f(n) ei ole polynomi, esim: T(n) = 2T(n/2) + 2ⁿ

Tämä lause on päälauseen edistynyt versio, jota voidaan käyttää määrittämään jako ja hallitse -algoritmien suoritusaika, jos toistuminen on seuraavassa muodossa:

missä n = ongelman koko
a = alitehtävien määrä rekursiossa ja a>= 1
n/b = kunkin osaongelman koko
b> 1, k>= 0 ja p on reaaliluku.

Sitten,

1. jos a> b^k, niin T(n) = θ(n^Hirsi_ba)
2. jos a = b^k, sitten
   (a) jos p> -1, niin T(n) = θ(n^Hirsi_baHirsi^p+1n)
   (b) jos p = -1, niin T(n) = θ(n^Hirsi_baloglogn)
   (c) jos p <-1, niin T(n) = θ(n^Hirsi_ba)
   
3. jos k, siis
   (a) jos p>= 0, niin T(n) = θ(n^kHirsi^sn)
   (b) jos p <0, niin T(n) = θ(n^k)
   

Aika monimutkaisuusanalyysi -

Esimerkki 1: Binäärihaku – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 ja p = 0
b^k= 1. Joten a = b^kja p> -1 [tapaus 2.(a)]
T(n) = θ(n^Hirsi_baHirsi^p+1n)
T(n) = θ(logn) Esimerkki-2: Yhdistä lajittelu – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Joten a = b^kja p> -1 [tapaus 2.(a)]
T(n) = θ(n^Hirsi_baHirsi^p+1n)
T(n) = θ(nlogn) Esimerkki-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Joten a k ja p = 0 [tapaus 3.(a)]
T(n) = θ(n^kHirsi^sn)
T(n) = θ(n²)

Esimerkki 4: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Joten a> b^k[Tapaus 1]
T(n) = θ(n^Hirsi_ba)
T(n) = θ(n^Hirsi₂3)

Esimerkki 5: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Joten a = b^k[Tapaus 2.(a)]
T(n) = θ(n^Hirsi_baHirsi^p+1n )
T(n) = θ(n^Hirsi₂2Hirsi³n)
T(n) = θ(nlog³n)

Esimerkki 6: T(n) = 2ⁿT(n/2) + nⁿ
Tätä toistumista ei voida ratkaista yllä olevalla menetelmällä, koska funktio ei ole muotoa T(n) = aT(n/b) + θ(n^kHirsi^sn)

GATE harjoituskysymykset –

• GATE-CS-2017 (sarja 2) | Kysymys 56
• GATE IT 2008 | Kysymys 42
• GATE CS 2009 | Kysymys 35

Tässä on joitain tärkeitä seikkoja, jotka on pidettävä mielessä Master-lauseen suhteen:

1. Jaa ja hallitse -toistuvat: Master Theorem on erityisesti suunniteltu ratkaisemaan toistuvuussuhteita, jotka syntyvät hajota ja hallitse -algoritmien analysoinnissa.
2. Toistumisen muoto: Päälause pätee toistuvuussuhteisiin muotoa T(n) = aT(n/b) + f(n), missä a, b ja f(n) ovat positiivisia funktioita ja n on koko ongelmasta.
3. Aikamonimutkaisuus: Päälause tarjoaa ehdot sille, että toistumisen ratkaisu on O(n^k):n muodossa jollekin vakiolle k, ja se antaa kaavan k:n arvon määrittämiseksi.
4. Edistynyt versio: Päälauseen edistynyt versio tarjoaa yleisemmän muodon lauseesta, joka pystyy käsittelemään perusmuotoa monimutkaisempia toistuvuussuhteita.
5. Rajoitukset: Päälause ei sovellu kaikkiin toistuvuussuhteisiin, eikä se välttämättä aina tarjoa tarkkaa ratkaisua tiettyyn toistumiseen.
6. Hyödyllinen työkalu: Päälause on rajoituksistaan ​​huolimatta hyödyllinen työkalu hajota ja hallitse -algoritmien aikamonimutkaisuuden analysointiin ja se tarjoaa hyvän lähtökohdan monimutkaisempien toistojen ratkaisemiseen.
7. Täydennettynä muilla tekniikoilla: Joissakin tapauksissa päälausetta on ehkä täydennettävä muilla tekniikoilla, kuten substituutiomenetelmällä tai iteraatiomenetelmällä tietyn toistuvuussuhteen ratkaisemiseksi kokonaan.