4.5 Die Master-Methode

Die Master-Methode ist ein zentrales Werkzeug, um rekursive Laufzeitgleichungen der Form

$$T(n)=a\cdot T(\frac{n}{b})+f(n)$$

abzuschätzen, wobei

• $a\ge 1$ (Anzahl der rekursiven Aufrufe),
• $b>1$ (Faktor, um den das Problem verkleinert wird),
• $f(n)$ eine nichtnegative Funktion, die den Aufwand pro Teilung beschreibt (z. B. das Zusammenführen bei Mergesort).

1. Beispiele rekursiver Algorithmen

1.1 Mergesort

• Idee: Teile das zu sortierende Array der Länge $n$ in zwei Hälften à $\frac{n}{2}$, sortiere diese rekursiv, und füge sie in $\mathrm{\Theta }(n)$ Zeit wieder zusammen.
• Rekursionsgleichung:

$$T(n)=2T(\frac{n}{2})+cn\text{für }n>1,T(1)=\mathrm{\Theta }(1).$$

1.2 Fakultät ${\displaystyle n!=n\cdot (n-1)!}$

• Rekursive Form (nicht Master-Methoden-tauglich, da sich das Problem nicht in gleich große Teile aufspaltet):

$$T(n)=T(n-1)+O(1),T(1)=O(1).$$

• Lösung: $T(n)=\mathrm{\Theta }(n)$. (In algorithmischer Praxis steht dahinter oft das direkte Produkt.)

1.3 Fibonacci-Zahlen

• Definition:

$$F(n)=F(n-1)+F(n-2),F(1)=F(2)=1.$$

• Exponential Laufzeit bei naiver Rekursion (keine Master-Form). Üblich ist jedoch eine dynamische Programmierung mit $O(n)$-Zeit.

1.4 (Erweiterter) euklidischer Algorithmus

• Erweiterter euklidischer Algorithmus findet $x,y$ derart, dass

$$gcd(a,b)=ax+by.$$

Beispielrechnung (mit kompletter Tabelle).

Wir rechnen $gcd(78,30)$ und finden zusätzlich die Darstellung $78x+30y=d$.
Der Algorithmus füllt typischerweise eine Tabelle folgender Art:

$i$	$a$	$b$	$q$	$r$	$x$	$y$
0	78	30	2	18	2	-5
1	30	18	1	12	-1	2
2	18	12	1	6	1	-1
3	12	6	2	0	0	1

Am Ende erhält man die Linearkombination $78\ast 2+30\ast (-5)=6$,
aus der $gcd(78,30)=6$ hervorgeht.

2. Beispiel: Rekursiver Algorithmus findeMax()

Wir wollen das Maximum eines Arrays der Länge $n$ finden.

1. Rekursions-Idee

   (A) Wenn n = 1: return z1
   (B) mitte := n/2
   (C) maxLinks  = findeMax( z1..z_mitte   )
   (D) maxRechts = findeMax( z_{mitte+1}..z_n )
   (E) return max( maxLinks, maxRechts )

2. Rekursionsgleichung

   • Falls $n=1$:   $T(1)=1\in O(1)$
   • Falls $n>1$:   Die Schritte (B) und (E) etc. sind konstant, plus 2 rekursive Aufrufe mit je $\frac{n}{2}$ Elementen.
   $$T(n)=\{\begin{array}{ll}1,& \text{falls n = }1\\ 2+2T(n/2),& \text{sonst}\end{array}$$

3. Die Master-Methode: Definition und drei Fälle

Für die Rekursion

$$T(n)=aT(\frac{n}{b})+f(n),$$

mit $a\ge 1$, $b>1$, unterscheidet man drei Fälle:

1. Fall 1: $f(n)$ wächst langsamer als $n^{{\log }_{b}a}$.
   Formal: $f(n)\in O(n^{{\log }_{b}a-\epsilon })$ für ein $\epsilon >0$.
   Dann

$$T(n)\in \mathrm{\Theta }(n^{{\log }_{b}a}).$$

2. Fall 2: $f(n)$ wächst wie $n^{{\log }_{b}a}$.
   Formal: $f(n)\in \mathrm{\Theta }(n^{{\log }_{b}a})$.
   Dann

$$T(n)\in \mathrm{\Theta }(n^{{\log }_{b}a}\log n).$$

3. Fall 3: $f(n)$ wächst schneller als $n^{{\log }_{b}a}$.
   Formal: $f(n)\in \mathrm{\Omega }(n^{{\log }_{b}a+\epsilon })$ und eine Regularitätsbedingung ist erfüllt.
   Dann

$$T(n)\in \mathrm{\Theta }(f(n)).$$

Beispielrechnungen:

1. Mergesort
   $T(n)=2T(\frac{n}{2})+cn,a=2,b=2,f(n)=cn.$

   • ${\log }_{b}a={\log }_{2}2=1$.
   • $f(n)=cn=\mathrm{\Theta }(n^1)$.
   • Übereinstimmung mit Fall 2
     $\Rightarrow T(n)\in \mathrm{\Theta }(n\log n)$.

2. findeMax()
   $T(n)=2T(\frac{n}{2})+O(1).$

   • ${\log }_{2}2=1$.
   • Hier ist $f(n)=O(1)=\mathrm{\Theta }(n^0)$. Das liegt unter $n^{{\log }_{2}2}=n^1$.
   • Fall 1 (mit $\epsilon =1$).
     $\Rightarrow T(n)\in \mathrm{\Theta }(n)$.

3. Vereinfachtes Bsp.:
   $T(n)=8T(\frac{n}{2})+100n^2.$

   • $a=8,b=2,{\log }_{b}a={\log }_{2}8=3$.
   • $f(n)=100n^2=\mathrm{\Theta }(n^2)$.
   • Vergleiche $n^2$ mit $n^3$.
   • $n^2$ wächst langsamer als $n^3$. → Fall 1
     $\Rightarrow T(n)\in \mathrm{\Theta }(n^3)$.

4. Beispiel (Fall 3):
   $T(n)=2T(\frac{n}{4})+10n⟶a=2,b=4,f(n)=10n.$

   • ${\log }_{b}a={\log }_4(2)=\frac{1}{2}$.
   • Somit ist $n^{{\log }_{b}a}=n^{1/2}=\sqrt{n}$.
   • Da $f(n)=10n$ schneller wächst als $\sqrt{n}$, wählen wir $\epsilon =\frac{1}{2}$. Zweite Bedingung (Regularitätsbedingung)
   • Für Fall 3 muss gelten:
   • $a\cdot f(\frac{n}{b})\le cf(n)\text{für ein konstantes }0<c<1.$

   Hier:

   • $a\cdot f(\frac{n}{4})=2\cdot 10\frac{n}{4}=5n.$
   • Wir vergleichen das mit $f(n)=10n$.\
   • $5n\le c\cdot 10n\Rightarrow c\ge 0.5.$\
   • Also kann man z.,B. $c=0.5$ wählen, was die Bedingung erfüllt ($c<1$).
     Fazit (Fall 3):
     $T(n)\in \mathrm{\Theta }(f(n))=\mathrm{\Theta }(n).$