1.2.6 Master-Theorem

Divide-and-Conquer

Viele effiziente Algorithmen folgen dem Schema „Teile und herrsche“. Bei Eingabegröße $n$:

1. Teilen: Das Problem wird in $a$ Teilprobleme der Größe $n/b$ zerlegt.
2. Rekursion: Jedes Teilproblem wird rekursiv gelöst, Kosten je $T(n/b)$.
3. Herrschen: Das Erzeugen der Teilprobleme und das Zusammenführen der Teillösungen kosten zusammen $f(n)$.

Das ergibt die Rekursionsgleichung

$T(n) = a\cdot T(n/b) + f(n).$

Was ist die Gesamtlaufzeit? Für viele Fälle beantwortet das das Master-Theorem.

Satz (Master-Theorem für Rekursionen)

Sei $T(n) = a\cdot T(n/b)+f(n)$ mit

• Konstanten $a\ge1$ und $b>1$,
• der Wasserscheiden-Konstante $\alpha := \log_b a$,
• einer Funktion $f(n)$ (der Aufteilungsfunktion),
• wobei $n/b$ als $\lfloor n/b\rfloor$ oder $\lceil n/b\rceil$ gelesen wird.

Dann gilt einer der folgenden Fälle:

Fall	Bedingung	Ergebnis
1	$f(n)=O(n^{\alpha-\varepsilon})$ für ein $\varepsilon>0$	$T(n)=\Theta(n^\alpha)$
2	$f(n)=\Theta(n^\alpha)$	$T(n)=\Theta(n^\alpha\log n)$
3	$f(n)=\Omega(n^{\alpha+\varepsilon})$ für ein $\varepsilon>0$ und $a\cdot f(n/b)\le c\cdot f(n)$ für ein $c<1$ und alle hinreichend großen $n$	$T(n)=\Theta(f(n))$

Intuition

Man stellt sich den Rekursionsbaum vor:

• Ebene 0: ein Problem der Größe $n$, Kosten $f(n)$.
• Ebene 1: $a$ Probleme der Größe $n/b$, Kosten $a\,f(n/b)$.
• Ebene $i$: $a^i$ Probleme der Größe $n/b^i$.
• Der Baum hat Tiefe $\log_b n$ und damit $a^{\log_b n} = n^{\log_b a} = n^\alpha$ Blätter.

$n^\alpha$ ist also die Arbeit „in den Blättern“, $f(n)$ die Arbeit „an der Wurzel“. Das Theorem vergleicht beide:

• Fall 1 – Blätter dominieren: $f$ wächst polynomiell langsamer als $n^\alpha$. Die Arbeit steckt unten im Baum, also $\Theta(n^\alpha)$.
• Fall 2 – Gleichstand: Jede der $\log n$ Ebenen kostet ungefähr gleich viel, $n^\alpha$. Insgesamt $\Theta(n^\alpha\log n)$.
• Fall 3 – Wurzel dominiert: $f$ wächst polynomiell schneller. Die Kosten nehmen nach unten geometrisch ab (das garantiert die Regularitätsbedingung $af(n/b)\le cf(n)$), die Wurzel bestimmt alles: $\Theta(f(n))$.

Zum Ausprobieren: Jeder Balken sind die Gesamtkosten einer Ebene des Rekursionsbaums. Wachsen sie nach unten (Fall 1), sind sie gleich (Fall 2) oder schrumpfen sie (Fall 3)?

a = 12345678b = 234f(n) = 1n^0.5nn^1.5n^2n^3

T(n) = 2·T(n/2) + n, α = log₂ 2 = 1. Ebene i hat 2ⁱ Teilprobleme der Größe n/2ⁱ und kostet ∝ (2/2¹)ⁱ = 1ⁱ.
k = α ⇒ Fall 2: jede der log n Ebenen kostet gleich viel ⇒ T(n) = Θ(n · log n).

Lücken

Das Theorem deckt nicht alle Fälle ab. Liegt $f$ „zwischen“ den Fällen, z.B. $f(n)=n^\alpha\log n$ (größer als $n^\alpha$, aber nicht um einen Faktor $n^\varepsilon$), ist es in dieser Form nicht anwendbar.

Beispiele (Ergänzung)

Algorithmus	Rekursion	$\alpha$	$f(n)$ vs. $n^\alpha$	Fall	Ergebnis
Binäre Suche	$T(n)=T(n/2)+1$	$\log_2 1=0$	$1=\Theta(n^0)$	2	$\Theta(\log n)$
Mergesort	$T(n)=2T(n/2)+n$	$\log_2 2=1$	$n=\Theta(n^1)$	2	$\Theta(n\log n)$
Divide-and-Conquer-Hülle	$T(n)=2T(n/2)+n$	$1$	$n=\Theta(n)$	2	$\Theta(n\log n)$
Karatsuba	$T(n)=3T(n/2)+n$	$\log_2 3\approx1{,}58$	$n=O(n^{1{,}58-\varepsilon})$	1	$\Theta(n^{1{,}58})$
–	$T(n)=2T(n/2)+n^2$	$1$	$n^2=\Omega(n^{1+\varepsilon})$, Regularität: $2(n/2)^2=\tfrac12n^2$ ✔	3	$\Theta(n^2)$

Bezug zu Kapitel 2: Die Divide-and-Conquer-Hülle teilt die Punkte an der Median-$x$-Koordinate in zwei Hälften, berechnet beide Hüllen rekursiv und verschmilzt sie in $O(n)$ über obere und untere Tangente. Nach Fall 2 ergibt das $\Theta(n\log n)$, also dieselbe Laufzeit wie Graham's Scan.