Het Master Theorem is een hulpmiddel dat wordt gebruikt om herhalingsrelaties op te lossen die ontstaan ​​bij de analyse van verdeel-en-heers-algoritmen. De Master Stelling biedt een systematische manier om herhalingsrelaties van de vorm op te lossen:

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

1. waarbij a, b en f(n) positieve functies zijn en n de omvang van het probleem is. De hoofdstelling biedt voorwaarden voor de oplossing van de herhaling in de vorm van O(n^k) voor een constante k, en het geeft een formule voor het bepalen van de waarde van k.
2. De geavanceerde versie van de Master Stelling biedt een meer algemene vorm van de stelling die herhalingsrelaties aankan die complexer zijn dan de basisvorm. De geavanceerde versie van de Master Stelling kan herhalingen met meerdere termen en complexere functies aan.
3. Het is belangrijk op te merken dat de Hoofdstelling niet van toepassing is op alle herhalingsrelaties, en dat deze niet altijd een exacte oplossing biedt voor een bepaald herhalingspatroon. Het is echter een nuttig hulpmiddel voor het analyseren van de tijdscomplexiteit van verdeel-en-heers-algoritmen en biedt een goed startpunt voor het oplossen van complexere herhalingen.

Master Theorem wordt gebruikt om de looptijd van algoritmen (verdeel en heers-algoritmen) te bepalen in termen van asymptotische notaties.
Beschouw een probleem dat wordt opgelost met behulp van recursie.

 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>

Het bovenstaande algoritme verdeelt het probleem in A deelproblemen, elk met de grootte n/b, en los ze recursief op om het probleem te berekenen. Het extra werk dat voor het probleem wordt gedaan, wordt gegeven door f(n), d.w.z. de tijd om de deelproblemen te creëren en hun resultaten te combineren in de bovenstaande procedure.

Dus volgens de hoofdstelling kan de looptijd van het bovenstaande algoritme worden uitgedrukt als:

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

waarbij n = omvang van het probleem
a = aantal deelproblemen in de recursie en a>= 1
n/b = omvang van elk subprobleem
f(n) = kosten van werk dat buiten de recursieve oproepen wordt gedaan, zoals het opdelen in subproblemen en de kosten van het combineren ervan om de oplossing te krijgen.

Niet alle herhalingsrelaties kunnen worden opgelost met behulp van de hoofdstelling, dat wil zeggen als

• T(n) is niet monotoon, bijvoorbeeld: T(n) = sin n
• f(n) is geen polynoom, bijv.: T(n) = 2T(n/2) + 2^N

Deze stelling is een geavanceerde versie van de hoofdstelling die kan worden gebruikt om de looptijd van verdeel-en-heers-algoritmen te bepalen als de herhaling de volgende vorm heeft: -

waarbij n = omvang van het probleem
a = aantal deelproblemen in de recursie en a>= 1
n/b = omvang van elk subprobleem
b> 1, k>= 0 en p is een reëel getal.

Dan,

1. als a> b^k, dan is T(n) = θ(n^loggen_BA)
2. als a = b^k, Dan
   (a) als p> -1, dan T(n) = θ(n^loggen_BAloggen^p+1N)
   (b) als p = -1, dan T(n) = θ(n^loggen_BAinloggen)
   (c) als p <-1, dan T(n) = θ(n^loggen_BA)
   
3. als een oke dan
   (a) als p>= 0, dan T(n) = θ(n^kloggen^PN)
   (b) als p <0, dan T(n) = θ(n^k)
   

Tijdcomplexiteitsanalyse –

Voorbeeld-1: Binaire zoekopdracht – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 en p = 0
B^k= 1. Dus a = b^ken p> -1 [Geval 2.(a)]
T(n) = θ(n^loggen_BAloggen^p+1N)
T(n) = θ(logn) Voorbeeld 2: Sortering samenvoegen – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
B^k= 2. Dus a = b^ken p> -1 [Geval 2.(a)]
T(n) = θ(n^loggen_BAloggen^p+1N)
T(n) = θ(nlogn) Voorbeeld 3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
B^k= 4. Dus, a k en p = 0 [Geval 3.(a)]
T(n) = θ(n^kloggen^PN)
T(n) = θ(n²)

Voorbeeld-4: T(n) = 3T(n/2) + log²N
a = 3, b = 2, k = 0, p = 2
B^k= 1. Dus a> b^k[Zaak 1]
T(n) = θ(n^loggen_BA)
T(n) = θ(n^loggen₂3)

Voorbeeld 5: T(n) = 2T(n/2) + nlog²N
a = 2, b = 2, k = 1, p = 2
B^k= 2. Dus a = b^k[Geval 2.(a)]
T(n) = θ(n^loggen_BAloggen^p+1N )
T(n) = θ(n^loggen₂2loggen³N)
T(n) = θ(nlog³N)

Voorbeeld-6: T(n) = 2^NT(n/2) + n^N
Deze herhaling kan niet worden opgelost met de bovenstaande methode, omdat de functie niet de vorm heeft T(n) = aT(n/b) + θ(n^kloggen^PN)

GATE Oefenvragen –

• GATE-CS-2017 (Set 2) | Vraag 56
• POORT IT 2008 | Vraag 42
• POORT CS 2009 | Vraag 35

Hier zijn enkele belangrijke punten waarmee u rekening moet houden met betrekking tot de Meesterstelling:

1. Verdeel-en-heers-herhalingen: Het Hoofdstelling is specifiek ontworpen om herhalingsrelaties op te lossen die ontstaan ​​bij de analyse van verdeel-en-heers-algoritmen.
2. Vorm van de herhaling: de hoofdstelling is van toepassing op herhalingsrelaties van de vorm T(n) = aT(n/b) + f(n), waarbij a, b en f(n) positieve functies zijn en n de grootte is van het probleem.
3. Tijdcomplexiteit: de hoofdstelling biedt voorwaarden voor de oplossing van de herhaling in de vorm van O(n^k) voor een constante k, en het geeft een formule voor het bepalen van de waarde van k.
4. Geavanceerde versie: De geavanceerde versie van de Hoofdstelling biedt een meer algemene vorm van de stelling die herhalingsrelaties aankan die complexer zijn dan de basisvorm.
5. Beperkingen: De hoofdstelling is niet van toepassing op alle herhalingsrelaties, en biedt mogelijk niet altijd een exacte oplossing voor een bepaald herhalingspatroon.
6. Handig hulpmiddel: Ondanks zijn beperkingen is het Hoofdstelling een nuttig hulpmiddel voor het analyseren van de tijdscomplexiteit van verdeel-en-heers-algoritmen en biedt het een goed startpunt voor het oplossen van complexere herhalingen.
7. Aangevuld met andere technieken: In sommige gevallen kan het nodig zijn om de Meesterstelling aan te vullen met andere technieken, zoals de substitutiemethode of de iteratiemethode, om een ​​gegeven herhalingsrelatie volledig op te lossen.