Mastersætningen er et værktøj, der bruges til at løse gentagelsesrelationer, der opstår i analysen af ​​del-og-hersk-algoritmer. Mastersætningen giver en systematisk måde at løse gentagelsesrelationer af formen:

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

1. hvor a, b og f(n) er positive funktioner og n er størrelsen af ​​problemet. Mastersætningen giver betingelser for, at løsningen af ​​gentagelsen er i form af O(n^k) for en eller anden konstant k, og den giver en formel til bestemmelse af værdien af ​​k.
2. Den avancerede version af Master Theorem giver en mere generel form af teoremet, der kan håndtere gentagelsesrelationer, der er mere komplekse end grundformen. Den avancerede version af Master Theorem kan håndtere gentagelser med flere termer og mere komplekse funktioner.
3. Det er vigtigt at bemærke, at Mastersætningen ikke er anvendelig på alle gentagelsesrelationer, og den giver muligvis ikke altid en nøjagtig løsning på en given gentagelse. Det er dog et nyttigt værktøj til at analysere tidskompleksiteten af ​​del-og-hersk algoritmer og giver et godt udgangspunkt for at løse mere komplekse gentagelser.

Master Theorem bruges til at bestemme køretiden for algoritmer (divide and conquer-algoritmer) i form af asymptotiske notationer.
Overvej et problem, der er løst ved hjælp af rekursion.

 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>

Ovenstående algoritme opdeler problemet i -en delproblemer, hver af størrelse n/b og løse dem rekursivt for at beregne problemet, og det ekstra arbejde, der udføres for problemet, er givet af f(n), dvs. tiden til at skabe delproblemerne og kombinere deres resultater i ovenstående procedure.

Så ifølge mastersætningen kan køretiden for ovenstående algoritme udtrykkes som:

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

hvor n = problemets størrelse
a = antal delproblemer i rekursionen og a>= 1
n/b = størrelsen af ​​hvert delproblem
f(n) = omkostningerne ved arbejde udført uden for de rekursive opkald som at opdele i underproblemer og omkostningerne ved at kombinere dem for at få løsningen.

Ikke alle gentagelsesrelationer kan løses ved brug af mastersætningen, dvs. hvis

• T(n) er ikke monoton, ex: T(n) = sin n
• f(n) er ikke et polynomium, f.eks.: T(n) = 2T(n/2) + 2ⁿ

Denne sætning er en forhåndsversion af hovedsætningen, der kan bruges til at bestemme løbetiden for dividere og erobre algoritmer, hvis gentagelsen er af følgende form: -

hvor n = problemets størrelse
a = antal delproblemer i rekursionen og a>= 1
n/b = størrelsen af ​​hvert delproblem
b> 1, k>= 0 og p er et reelt tal.

Derefter,

1. hvis a> b^k, så T(n) = θ(n^log_b-en)
2. hvis a = b^k, derefter
   (a) hvis p> -1, så er T(n) = θ(n^log_b-enlog^p+1n)
   (b) hvis p = -1, så er T(n) = θ(n^log_b-enloglogn)
   (c) hvis p <-1, så er T(n) = θ(n^log_b-en)
   
3. hvis en k, så
   (a) hvis p>= 0, så er T(n) = θ(n^klog^sn)
   (b) hvis p <0, så er T(n) = θ(n^k)
   

Tidskompleksitetsanalyse –

Eksempel-1: Binær søgning – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 og p = 0
b^k= 1. Altså a = b^kog p> -1 [tilfælde 2.(a)]
T(n) = θ(n^log_b-enlog^p+1n)
T(n) = θ(logn) Eksempel-2: Flet sortering – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
b^k= 2. Altså a = b^kog p> -1 [tilfælde 2.(a)]
T(n) = θ(n^log_b-enlog^p+1n)
T(n) = θ(nlogn) Eksempel-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
b^k= 4. Altså en k og p = 0 [tilfælde 3.(a)]
T(n) = θ(n^klog^sn)
T(n) = θ(n²)

Eksempel-4: T(n) = 3T(n/2) + log²n
a = 3, b = 2, k = 0, p = 2
b^k= 1. Altså a> b^k[Case 1]
T(n) = θ(n^log_b-en)
T(n) = θ(n^log₂3)

Eksempel-5: T(n) = 2T(n/2) + nlog²n
a = 2, b = 2, k = 1, p = 2
b^k= 2. Altså a = b^k[Sag 2.(a)]
T(n) = θ(n^log_b-enlog^p+1n)
T(n) = θ(n^log₂2log³n)
T(n) = θ(nlog³n)

Eksempel-6: T(n) = 2ⁿT(n/2) + nⁿ
Denne gentagelse kan ikke løses ved hjælp af ovenstående metode, da funktionen ikke har formen T(n) = aT(n/b) + θ(n^klog^sn)

GATE øvelsesspørgsmål –

• GATE-CS-2017 (Sæt 2) | Spørgsmål 56
• GATE IT 2008 | Spørgsmål 42
• GATE CS 2009 | Spørgsmål 35

Her er nogle vigtige punkter at huske på i forbindelse med Master Theorem:

1. Del-og-hersk-gentagelser: Mastersætningen er specifikt designet til at løse gentagelsesrelationer, der opstår i analysen af ​​opdel-og-hersk-algoritmer.
2. Gentagelsens form: Mastersætningen gælder for gentagelsesrelationer af formen T(n) = aT(n/b) + f(n), hvor a, b og f(n) er positive funktioner og n er størrelsen af problemet.
3. Tidskompleksitet: Mastersætningen giver betingelser for, at løsningen af ​​gentagelsen er i form af O(n^k) for en eller anden konstant k, og den giver en formel til bestemmelse af værdien af ​​k.
4. Avanceret version: Den avancerede version af Master Theorem giver en mere generel form af teoremet, der kan håndtere gentagelsesrelationer, der er mere komplekse end grundformen.
5. Begrænsninger: Mastersætningen er ikke anvendelig for alle gentagelsesrelationer, og den giver muligvis ikke altid en nøjagtig løsning på en given gentagelse.
6. Nyttigt værktøj: På trods af sine begrænsninger er Master Theorem et nyttigt værktøj til at analysere tidskompleksiteten af ​​del-og-hersk algoritmer og giver et godt udgangspunkt for at løse mere komplekse gentagelser.
7. Suppleret med andre teknikker: I nogle tilfælde skal Mastersætningen muligvis suppleres med andre teknikker, såsom substitutionsmetoden eller iterationsmetoden, for fuldstændig at løse en given gentagelsesrelation.