4. Master-Methode¶
Die Master-Methode liefert ein Black-Box Verfahren zu Bestimmung der Laufzeit von vielen rekursiven Algorithmen.
Die hier verwendete Version der Master-Methode ist aus T. Roughgarden, Algorithms Illuminated, Part 1: The Basics.
Master-Methode als Black-Box¶
4.2.1 Standard-Rekursionsformat¶
Basis Fall: $T(n)$ ist maximal konstant (für hinreichend kleine $n$)
Allgemeiner Fall für größere Werte von $n$: $$ T(n) \leq a \cdot T \left(\frac{n}{b}\right) + O(n^d) $$
Parameter:
- $a$: Anzahl der rekursiven Aufrufe
- $b$: Längen-Schrumpffaktor
- $d$: Laufzeit-Exponent des Kombinationsschrittes (combine step) (und Daten-Aufspalten etc.)
Hinweis:
Genaugenommen muss $\frac{n}{b}$ nicht immer eine Ganzzahl sein. Exakt müsste man technisch betrachtet ggf. mit der floor- oder der ceiling-Funktion arbeiten. Dies hat aber keinen Einfluss auf das asymptotische Verhalten, siehe [Corman], Kapitel 4.4.2.
Theorem 4.1¶
Wenn $T(n)$ im Standard-Rekursionsformat gegeben ist mit den Parametern $a \geq 1$, $b > 1$ und $d \geq 0$, dann gilt für die Laufzeit
\begin{align} T(n) \in \begin{cases} O(n^d \log n) & \text{wenn} & a=b^d & \text{[Fall 1]}\\ O(n^d) & \text{wenn} & a<b^d & \text{[Fall 2]}\\ O(n^{\log_b a}) & \text{wenn} & a>b^d & \text{[Fall 3]}\\ \end{cases} \end{align}Nebenbemerkung:
- Für den allgemeineren Fall des Master-Theorems mit $$T(n) = a \cdot T \left(\frac{n}{b}\right) + f(n)$$ siehe Kapitel 4.3 des Lehrbuches [Corman].
- Eine weitere Generalisierung ist die Akra–Bazzi Methode, die auch angewandt werden kann, falls die verschiedenen Unterprobleme unterschiedlich groß sind.
Beispiel: RectIntMul¶
$$
T(n) \leq 4 \cdot T \left(\frac{n}{2}\right) + O(n)
$$Parameter:
- $a = 4$
- $b = 2$
- $d = 1$ (mit Nullen auffüllen und der Addition)
$\Rightarrow \text{Fall 3}$: $T(n) = O(n^{\log_2 4}) = O(n^{2})$
Wieviele Unterprobleme hat man auf der Stufe $j$ eines Rekursionsbaums?
Wie groß ist das Array eines Unterproblems, das auf der Stufe $j$ eines Rekursionsbaums gelöst werden muss, wenn das Orginalproblem die Länge $n$ hat?
- $a^j$
- $l_j = \frac{n}{b^j}$
bei uns mit $f(n)=cn^d$
Arbeit auf der Stufe $j$¶
$$ \text{ Arbeit auf der Stufe } j \leq a^j \cdot c \left[\frac{n}{b^j} \right]^d $$- $a^j$: Anzahl der Unterprobleme auf Stufe $j$
- $c \left[\frac{n}{b^j}\right]^d$: Arbeit pro Unterproblem auf Stufe $j$
Separieren der Teile, die vom Level $j$ abhängen:
$$ \text{ Arbeit auf der Stufe } j \leq cn^d \cdot \left[\frac{a}{b^d} \right]^j $$in $$ \text{ Arbeit auf einer Stufe } j \leq cn^d \cdot \left[\frac{a}{b^d} \right]^j $$
ist
$$\frac{a}{b^d}$$das kritische Verhältnis. Dieses bestimmt, ob die Arbeit auf einer Stufe gleichbleibt, wächst oder fällt.
Gesamte Arbeit¶
Die gesamte Arbeit ist die Summe, die auf den einzelnen Stufen geleistet wird:
$$ \text{ Gesamte Arbeit} \leq cn^d \cdot \sum_{j=0}^{\log_b n}\left[\frac{a}{b^d} \right]^j $$Drei Fälle¶
- $a$: rate of subproblem proliferation (RSP)
- $b^d$: rate of work shrinkage (RWS)
Drei Fälle:
- RSP = RWS, d.h. $a = b^d$
- RSP < RWS, d.h. $a < b^d$
- RSP > RWS, d.h. $a > b^d$
Was bedeutet dies für die Arbeit, die auf den einzelnen Levels $j$ verrichtet werden muss, mit zunehmenden $j$?
- RSP = RWS: die Arbeit pro Stufe ist gleich.
- RSP < RWS, weniger Arbeit mit zunehmenden $j$.
- RSP > RWS, mehr Arbeit zunehmenden $j$.
1. Fall RSP = RWS, d.h $a = b^d$¶
Die Arbeit pro Stufe ist gleich!
- Arbeit pro Level $O(n^d)$
- Anzahl der Levels $= 1+\log_b n = O(\log n)$
Gesamte Arbeit = Summe der Arbeit pro Sublevel = $O(n^d \log n)$
2. Fall RSP < RWS, d.h. $a < b^d$¶
Weniger Arbeit mit zunehmender Stufe $j$ (Level).
Annahme: Die Arbeit auf Level Null ist (sehr) dominant, d.h. die Gesamtarbeit wird dadurch bestimmt:
Gesamte Arbeit = $O(n^d)$
3. Fall RSP > RWS, d.h. $a > b^d$¶
Mehr Arbeit mit zunehmenden $j$ (Level).
Annahme: Die Arbeit auf dem höchsten Level sehr dominant ist,
d.h. diese bestimmt die Gesamtarbeit:
- $a^j$ Knoten pro Level
- $j$ des höchsten Levels ist $j_m = \log_b n$
$\Rightarrow$ Anzahl der Knoten des höchsten Levels ist $a^{\log_b n}$
Auf dem höchstes Level wird der Base-Case aufgeführt: $O(1)$ pro Blatt des Rekursionsbaumes
mit der Identität $a^{\log_b n} = n^{\log_b a}$
Gesamte Arbeit = $O(n^{\log_b a})$
Beweis¶
- Die obige Abschätzung basiert auf der Dominanzannahme.
- Der Beweis von Theorem 4.1 führt zum gleichen Ergebnis.
Fall 1:¶
mit $a=b^d$
$$ \text{ Gesamte Arbeit} \leq c n^d \cdot \sum_{j=0}^{\log_b n}\left[\frac{a}{b^d} \right]^j = c n^d \cdot \left(1+1+\dots+1 \right) = c n^d (1+\log_b n) $$$\Rightarrow$ $$\text{ Gesamte Arbeit} \in O(n^d \log n)$$
Geometrische Reihe¶
$$ 1+r+r^2+\dots + r^k = \frac{1-r^{k+1}}{1-r} $$bei uns ist $r = \frac{a}{b^d}$
Fall 2¶
$\frac{a}{b^d} < 1$, d.h. $r<1$
$$ 1+r+r^2+\dots + r^k \leq \frac{1}{1-r} = const. \text{(unabhängig von k)} $$also $$\sum_{j=0}^{\log_b n}\left[\frac{a}{b^d} \right]^j \leq \frac{1}{1-\frac{a}{b^d}} = const. \text{(unabhängig von $\log_b n$ bzw. $n$)} $$
$$ \text{ Gesamte Arbeit} \leq c n^d \cdot \sum_{j=0}^{\log_b n}\left[\frac{a}{b^d} \right]^j \leq c' n^d $$$$ \text{ Gesamte Arbeit} \in O(n^d) $$Fall 3¶
$\frac{a}{b^d} > 1$, d.h. $r>1$
$$ 1+r+r^2+\dots + r^k = \frac{r^{k+1}-1}{r-1} \leq \frac{r^{k+1}}{r-1} = r^k \cdot \frac{r}{r-1} $$- $r^k$ entspricht dem letzten Term der Summe
- Die Summe ist maximal $r^k \cdot const$. Dabei heißt $const$ hier $\text{unabhängig von k}$
also $$ \text{ Gesamte Arbeit} \leq c n^d \cdot \sum_{j=0}^{\log_b n}\left[\frac{a}{b^d} \right]^j \leq c n^d \left(\frac{a}{b^d}\right)^{\log_b n} \frac{\frac{a}{b^d}}{\frac{a}{b^d}-1} = c' n^d \left(\frac{a}{b^d}\right)^{\log_b n}$$
mit $\left(b^{-d}\right)^{\log_b n} = b^{-d \log_b n} = \left(b^{\log_b n}\right)^{-d} = n^{-d}$
und $a^{\log_b n} = n^{\log_b a}$
Bemerkung: Dass $a^{\log_b n} = n^{\log_b a}$ ist sieht man, wenn man beide Seiten logarithmiert (mit $\log_b$):
$$ \log_b (a^{\log_b n}) = \log_b(n^{\log_b a})$$Anwenden des Potenzgesetz für Logarithmen:
$$\log_b n \cdot \log_b a = \log_b a \cdot \log_b n$$Da der Logarithmus eine monoton-steigende Funktion ist, muss daher $a^{\log_b n} = n^{\log_b a}$ gelten.
Zusammenfassung¶
Das Master-Methode liefert eine obere Grenze für die asymptotische Laufzeit rekursiver Algorithmen, wenn diese für den Algorithmus im Standard-Rekursionsformat vorliegen. Die obere Grenze kann dann einfach als Black-Box Methode bestimmt werden.