In diesem Tutorial erfahren Sie, was der Hauptsatz ist und wie er zum Lösen von Wiederholungsrelationen verwendet wird.
Die Master-Methode ist eine Formel zum Lösen von Wiederholungsrelationen der Form:
T (n) = aT (n / b) + f (n), wobei n = Größe der Eingabe a = Anzahl der Teilprobleme in der Rekursion n / b = Größe jedes Teilproblems. Es wird angenommen, dass alle Teilprobleme die gleiche Größe haben. f (n) = Kosten der außerhalb des rekursiven Aufrufs geleisteten Arbeit, einschließlich der Kosten für die Aufteilung des Problems und der Kosten für die Zusammenführung der Lösungen. Hier sind a ≧ 1 und b> 1 Konstanten, und f (n) ist asymptotisch positiv Funktion.
Eine asymptotisch positive Funktion bedeutet, dass wir für einen ausreichend großen Wert von n haben f(n)> 0.
Der Hauptsatz wird verwendet, um die zeitliche Komplexität von Wiederholungsrelationen (Divide and Conquer-Algorithmen) auf einfache und schnelle Weise zu berechnen.
Hauptsatz
Wenn a ≧ 1und b> 1Konstanten sind und f(n)eine asymptotisch positive Funktion ist, dann ist die zeitliche Komplexität einer rekursiven Beziehung gegeben durch
T (n) = aT (n / b) + f (n) wobei T (n) die folgenden asymptotischen Grenzen hat: 1. Wenn f (n) = O (n log b a - ϵ ), dann ist T (n ) = Θ (n log b a ). 2. Wenn f (n) = Θ (n log b a ), dann ist T (n) = Θ (n log b a * log n). 3. Wenn f (n) = Ω (n log b a + ϵ ), dann ist T (n) = Θ (f (n)). ϵ> 0 ist eine Konstante.
Jede der oben genannten Bedingungen kann wie folgt interpretiert werden:
- Wenn die Kosten für die Lösung der Unterprobleme auf jeder Ebene um einen bestimmten Faktor steigen, wird der Wert von
f(n)polynomial kleiner als . Somit wird die zeitliche Komplexität durch die Kosten der letzten Ebene unterdrückt, d. H.nlogb anlogb a - Wenn die Kosten für das Teilproblem auf jeder Ebene zu lösen nahezu gleich ist, dann wird der Wert
f(n)sein wird . Somit ist die zeitliche Komplexität mal die Gesamtzahl der Ebenen, d. H.nlogb af(n)nlogb a * log n - Wenn die Kosten für die Lösung der Teilprobleme auf jeder Ebene um einen bestimmten Faktor sinken, wird der Wert von
f(n)polynomial größer als . Somit wird die zeitliche Komplexität durch die Kosten von unterdrückt .nlogb af(n)
Gelöstes Beispiel des Master-Theorems
T (n) = 3T (n / 2) + n2 Hier ist a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≤ 1,58 <2 dh. f (n) <n log b a + ϵ , wobei ϵ eine Konstante ist. Fall 3 impliziert hier. Somit ist T (n) = f (n) = Θ (n 2 )
Einschränkungen des Master-Theorems
Der Hauptsatz kann nicht verwendet werden, wenn:
- T (n) ist nicht monoton. z.B.
T(n) = sin n f(n)ist kein Polynom. z.B.f(n) = 2n- a ist keine Konstante. z.B.
a = 2n a < 1
