Das Master-Theorem ist ein Werkzeug zur Lösung von Wiederholungsbeziehungen, die bei der Analyse von Divide-and-Conquer-Algorithmen auftreten. Das Master-Theorem bietet eine systematische Möglichkeit zur Lösung von Wiederholungsrelationen der Form:

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

1. wobei a, b und f(n) positive Funktionen sind und n die Größe des Problems ist. Das Master-Theorem liefert Bedingungen für die Lösung der Wiederholung in der Form O(n^k) für eine Konstante k und gibt eine Formel zur Bestimmung des Werts von k an.
2. Die erweiterte Version des Master-Theorems bietet eine allgemeinere Form des Theorems, die Wiederholungsbeziehungen verarbeiten kann, die komplexer sind als die Grundform. Die erweiterte Version des Master-Theorems kann Wiederholungen mit mehreren Termen und komplexeren Funktionen verarbeiten.
3. Es ist wichtig zu beachten, dass das Master-Theorem nicht auf alle Wiederholungsbeziehungen anwendbar ist und möglicherweise nicht immer eine exakte Lösung für eine bestimmte Wiederholung liefert. Es ist jedoch ein nützliches Werkzeug zur Analyse der zeitlichen Komplexität von Divide-and-Conquer-Algorithmen und bietet einen guten Ausgangspunkt für die Lösung komplexerer Wiederholungen.

Der Mastersatz wird verwendet, um die Laufzeit von Algorithmen (Divide-and-Conquer-Algorithmen) anhand asymptotischer Notationen zu bestimmen.
Stellen Sie sich ein Problem vor, das durch Rekursion gelöst wird.

 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>

Der obige Algorithmus unterteilt das Problem in A Teilprobleme, jedes mit der Größe n/b, und lösen Sie sie rekursiv, um das Problem zu berechnen. Die zusätzliche Arbeit, die für das Problem geleistet wird, ist durch f(n) gegeben, d. h. die Zeit, um die Teilprobleme zu erstellen und ihre Ergebnisse im obigen Verfahren zu kombinieren.

Gemäß dem Master-Theorem kann die Laufzeit des obigen Algorithmus ausgedrückt werden als:

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

wobei n = Größe des Problems
a = Anzahl der Teilprobleme in der Rekursion und a>= 1
n/b = Größe jedes Teilproblems
f(n) = Kosten der außerhalb der rekursiven Aufrufe geleisteten Arbeit, wie z. B. die Aufteilung in Teilprobleme und Kosten für deren Kombination, um die Lösung zu erhalten.

Nicht alle Wiederholungsbeziehungen können mit dem Hauptsatz gelöst werden, d. h. wenn

• T(n) ist nicht monoton, z. B.: T(n) = sin n
• f(n) ist kein Polynom, z. B.: T(n) = 2T(n/2) + 2^N

Dieser Satz ist eine Weiterentwicklung des Hauptsatzes, der zur Bestimmung der Laufzeit von Divide-and-Conquer-Algorithmen verwendet werden kann, wenn die Wiederholung die folgende Form hat:

wobei n = Größe des Problems
a = Anzahl der Teilprobleme in der Rekursion und a>= 1
n/b = Größe jedes Teilproblems
b> 1, k>= 0 und p ist eine reelle Zahl.

Dann,

1. wenn a> b^k, dann T(n) = θ(n^Protokoll_BA)
2. wenn a = b^k, Dann
   (a) wenn p> -1, dann T(n) = θ(n^Protokoll_BAProtokoll^p+1N)
   (b) wenn p = -1, dann ist T(n) = θ(n^Protokoll_BAloglogn)
   (c) wenn p <-1, dann T(n) = θ(n^Protokoll_BA)
   
3. wenn ein k, dann
   (a) wenn p>= 0, dann T(n) = θ(n^kProtokoll^PN)
   (b) wenn p <0, dann T(n) = θ(n^k)
   

Zeitkomplexitätsanalyse –

Beispiel 1: Binäre Suche – T(n) = T(n/2) + O(1)
a = 1, b = 2, k = 0 und p = 0
B^k= 1. Also, a = b^kund p> -1 [Fall 2.(a)]
T(n) = θ(n^Protokoll_BAProtokoll^p+1N)
T(n) = θ(logn) Beispiel 2: Zusammenführungssortierung – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
B^k= 2. Also, a = b^kund p> -1 [Fall 2.(a)]
T(n) = θ(n^Protokoll_BAProtokoll^p+1N)
T(n) = θ(nlogn) Beispiel-3: T(n) = 3T(n/2) + n²
a = 3, b = 2, k = 2, p = 0
B^k= 4. Also, a k und p = 0 [Fall 3.(a)]
T(n) = θ(n^kProtokoll^PN)
T(n) = θ(n²)

Beispiel 4: T(n) = 3T(n/2) + log²N
a = 3, b = 2, k = 0, p = 2
B^k= 1. Also, a> b^k[Fall 1]
T(n) = θ(n^Protokoll_BA)
T(n) = θ(n^{Protokoll₂3})

Beispiel-5: T(n) = 2T(n/2) + nlog²N
a = 2, b = 2, k = 1, p = 2
B^k= 2. Also, a = b^k[Fall 2.(a)]
T(n) = θ(n^Protokoll_BAProtokoll^p+1N )
T(n) = θ(n^{Protokoll₂2}Protokoll³N)
T(n) = θ(nlog³N)

Beispiel-6: T(n) = 2^NT(n/2) + n^N
Diese Wiederholung kann mit der obigen Methode nicht gelöst werden, da die Funktion nicht die Form T(n) = aT(n/b) + θ(n) hat^kProtokoll^PN)

GATE-Übungsfragen –

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

Hier sind einige wichtige Punkte, die Sie in Bezug auf das Master-Theorem beachten sollten:

1. Divide-and-Conquer-Rekursionen: Das Master-Theorem wurde speziell zur Lösung von Rekurrenzbeziehungen entwickelt, die bei der Analyse von Divide-and-Conquer-Algorithmen auftreten.
2. Form der Wiederholung: Das Master-Theorem gilt für Wiederholungsbeziehungen der Form T(n) = aT(n/b) + f(n), wobei a, b und f(n) positive Funktionen sind und n die Größe ist von dem Problem.
3. Zeitkomplexität: Das Master-Theorem liefert Bedingungen für die Lösung der Wiederholung in der Form O(n^k) für eine Konstante k und gibt eine Formel zur Bestimmung des Werts von k an.
4. Erweiterte Version: Die erweiterte Version des Master-Theorems bietet eine allgemeinere Form des Theorems, die Wiederholungsbeziehungen verarbeiten kann, die komplexer sind als die Grundform.
5. Einschränkungen: Das Master-Theorem ist nicht auf alle Wiederholungsbeziehungen anwendbar und liefert möglicherweise nicht immer eine exakte Lösung für eine bestimmte Wiederholung.
6. Nützliches Werkzeug: Trotz seiner Einschränkungen ist das Master-Theorem ein nützliches Werkzeug zur Analyse der zeitlichen Komplexität von Divide-and-Conquer-Algorithmen und bietet einen guten Ausgangspunkt für die Lösung komplexerer Wiederholungen.
7. Ergänzt durch andere Techniken: In einigen Fällen muss das Master-Theorem möglicherweise durch andere Techniken wie die Substitutionsmethode oder die Iterationsmethode ergänzt werden, um eine bestimmte Wiederholungsbeziehung vollständig zu lösen.