Lektion 1.3

Das Master-Theorem

40 min Lesezeit
Lesen anpassen

Nach dieser Lektion kannst du

  • eine Teile-und-herrsche-Rekurrenz T(n)=a T(n/b)+f(n)T(n) = a\,T(n/b) + f(n) an einem Algorithmus ablesen,

  • mit dem Master-Theorem entscheiden, welcher der drei Fälle vorliegt, und die Lösung angeben,

  • die drei Fälle aus dem Rekursionsbaum mit geometrischen Reihen begründen,

  • die Laufzeiten von binärer Suche, Mergesort, Karatsuba und Strassen herleiten,

  • Rekurrenzen erkennen, auf die das Theorem nicht passt, und sie anders lösen.

Vorausgesetzt: Laufzeit messen: Operationen zählen und O-Notation, Rekursion und Rekurrenzgleichungen

Zwei Zahlen mit je nn Ziffern multiplizierst du in der Schule, indem du jede Ziffer der einen mit jeder Ziffer der anderen malnimmst. Das sind n2n^2 Ziffernprodukte. Geht es schneller, wenn man nach dem Prinzip Teile und herrsche vorgeht?

Teile jede Zahl in eine vordere und eine hintere Hälfte mit je m=n/2m = n/2 Ziffern: x=x1⋅10m+x0x = x_1 \cdot 10^m + x_0 und y=y1⋅10m+y0y = y_1 \cdot 10^m + y_0. Ausmultiplizieren ergibt xy=x1y1⋅102m+(x1y0+x0y1)⋅10m+x0y0x y = x_1 y_1 \cdot 10^{2m} + (x_1 y_0 + x_0 y_1) \cdot 10^m + x_0 y_0. Das sind vier Produkte von Zahlen mit n/2n/2 Ziffern, dazu Additionen und Verschiebungen um Zehnerstellen, die zusammen linear viel kosten. Für die Laufzeit gilt also T(n)=4 T(n/2)+nT(n) = 4\,T(n/2) + n, wenn wir die lineare Arbeit mit Kosten nn ansetzen.

Solche Rekurrenzen entstehen bei jedem Teile-und-herrsche-Verfahren, nur mit anderen Zahlen. Statt jedes Mal einen Rekursionsbaum zu zeichnen, wollen wir ein Rezept, das die Lösung direkt aus den Zahlen abliest. Dieses Rezept ist das Master-Theorem.

Vermute zuerst

Für die Multiplikation mit vier halb so großen Teilprodukten gilt T(1)=1T(1) = 1 und T(n)=4 T(n/2)+nT(n) = 4\,T(n/2) + n. Wie schnell wächst T(n)T(n)?

Definition

Teile-und-herrsche-Rekurrenz

Ein Verfahren, das ein Problem der Größe nn in aa Teilprobleme der Größe n/bn/b zerlegt, sie rekursiv löst und dafür außerhalb der Aufrufe die Arbeit f(n)f(n) leistet (Teilen und Zusammensetzen), hat die Laufzeit

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

Dabei sind a≥1a \ge 1 und b>1b > 1 Konstanten, f(n)≥0f(n) \ge 0, und T(n)T(n) ist für kleine nn eine positive Konstante. Ist n/bn/b keine ganze Zahl, wird auf- oder abgerundet; das ändert das Ergebnis des Satzes unten nicht.

Verfahrenaabbf(n)f(n)
binäre Suche112211
Mergesort2222nn
Multiplikation mit vier Teilprodukten4422nn

Keine Rekurrenz dieser Form ist T(n)=T(n−1)+nT(n) = T(n-1) + n: Das Problem wird um 11 kleiner, nicht um einen festen Faktor bb. Ebenso wenig T(n)=n T(n/2)+1T(n) = n\,T(n/2) + 1, denn die Zahl der Teilprobleme ist keine Konstante.

Schritt für Schritt

Der Rekursionsbaum allgemein

Sei nn eine Potenz von bb, also n=bLn = b^L mit L=log⁡bnL = \log_b n, und sei T(1)=1T(1) = 1.

  1. Auf Ebene jj liegen aja^j Knoten, denn jeder Knoten hat aa Kinder. Jeder hat die Größe n/bjn/b^j und kostet selbst f(n/bj)f(n/b^j).

Schritt 1 von 4
Satz

Master-Theorem

Seien a≥1a \ge 1 und b>1b > 1 Konstanten, f(n)≥0f(n) \ge 0, und TT erfülle T(n)=a T(n/b)+f(n)T(n) = a\,T(n/b) + f(n) für alle großen nn (mit n/bn/b auf- oder abgerundet), wobei T(n)T(n) für kleine nn eine positive Konstante ist. Sei p=log⁡bap = \log_b a.

  • Fall 1: Gibt es ein ε>0\varepsilon > 0 mit f∈O(np−ε)f \in O(n^{p - \varepsilon}), so ist T∈Θ(np)T \in \Theta(n^p). Die Blätter dominieren.
  • Fall 2: Ist f∈Θ(np)f \in \Theta(n^p), so ist T∈Θ(nplog⁡n)T \in \Theta(n^p \log n). Alle Ebenen kosten etwa gleich viel.
  • Fall 3: Gibt es ein ε>0\varepsilon > 0 mit f∈Ω(np+ε)f \in \Omega(n^{p + \varepsilon}) und eine Konstante c<1c < 1 mit a f(n/b)≤c f(n)a\,f(n/b) \le c\,f(n) für alle großen nn (Regularitätsbedingung), so ist T∈Θ(f)T \in \Theta(f). Die Wurzel dominiert.

In Fall 1 und 3 muss ff also um einen Faktor nεn^{\varepsilon} kleiner beziehungsweise größer sein als npn^p, nicht nur irgendwie kleiner oder größer.

T(n)∈{Θ(np)Fall 1: f∈O(np−ε)Θ(nplog⁡n)Fall 2: f∈Θ(np)Θ(f)Fall 3: f∈Ω(np+ε) und regula¨rT(n) \in \begin{cases} \Theta(n^{p}) & \text{Fall 1: } f \in O(n^{p-\varepsilon}) \\ \Theta(n^{p}\log n) & \text{Fall 2: } f \in \Theta(n^{p}) \\ \Theta(f) & \text{Fall 3: } f \in \Omega(n^{p+\varepsilon}) \text{ und regulär} \end{cases}
Beispiel

Binäre Suche und Mergesort

Binäre Suche: T(n)=T(n/2)+1T(n) = T(n/2) + 1. Hier ist a=1a = 1, b=2b = 2, p=log⁡21=0p = \log_2 1 = 0, und f(n)=1=n0∈Θ(np)f(n) = 1 = n^0 \in \Theta(n^p). Fall 2 liefert T∈Θ(n0log⁡n)=Θ(log⁡n)T \in \Theta(n^0 \log n) = \Theta(\log n), wie in der letzten Lektion durch Abwickeln.

Mergesort: T(n)=2 T(n/2)+nT(n) = 2\,T(n/2) + n. Hier ist p=log⁡22=1p = \log_2 2 = 1 und f(n)=n∈Θ(n1)f(n) = n \in \Theta(n^1). Wieder Fall 2:

T(n)∈Θ(nlog⁡n)T(n) \in \Theta(n \log n)

In beiden Fällen kostet jede Ebene des Rekursionsbaums gleich viel (11 beziehungsweise nn), und es gibt log⁡n\log n Ebenen. Das ist die Anschauung von Fall 2.

Kurz geprüft

Welcher Fall des Master-Theorems liegt bei T(n)=3 T(n/4)+nT(n) = 3\,T(n/4) + n vor?

Beispiel

Karatsuba: drei statt vier Teilprodukte

Die Multiplikation mit vier Teilprodukten aus der Einleitung ist nach Fall 1 in Θ(n2)\Theta(n^2): p=log⁡24=2p = \log_2 4 = 2 und f(n)=n∈O(n2−1)f(n) = n \in O(n^{2-1}). Anatoli Karatsuba fand 1960 einen Trick: Der mittlere Koeffizient x1y0+x0y1x_1 y_0 + x_0 y_1 lässt sich aus einem weiteren Produkt gewinnen, denn (x1+x0)(y1+y0)=x1y1+x1y0+x0y1+x0y0(x_1 + x_0)(y_1 + y_0) = x_1 y_1 + x_1 y_0 + x_0 y_1 + x_0 y_0. Man braucht also nur x1y1x_1 y_1, x0y0x_0 y_0 und (x1+x0)(y1+y0)(x_1 + x_0)(y_1 + y_0):

xy=x1y1⋅102m+((x1+x0)(y1+y0)−x1y1−x0y0)⋅10m+x0y0x y = x_1 y_1 \cdot 10^{2m} + \bigl((x_1 + x_0)(y_1 + y_0) - x_1 y_1 - x_0 y_0\bigr) \cdot 10^m + x_0 y_0

Beispiel 12⋅3412 \cdot 34 mit m=1m = 1: x1y1=1⋅3=3x_1 y_1 = 1 \cdot 3 = 3, x0y0=2⋅4=8x_0 y_0 = 2 \cdot 4 = 8, (1+2)(3+4)=21(1 + 2)(3 + 4) = 21, Mittelteil 21−3−8=1021 - 3 - 8 = 10. Ergebnis 3⋅100+10⋅10+8=4083 \cdot 100 + 10 \cdot 10 + 8 = 408.

Die zusätzlichen Additionen kosten nur linear viel, also T(n)=3 T(n/2)+nT(n) = 3\,T(n/2) + n. Nun ist p=log⁡23≈1,585p = \log_2 3 \approx 1{,}585 und f(n)=n∈O(np−0,5)f(n) = n \in O(n^{p - 0{,}5}). Fall 1 ergibt T∈Θ(nlog⁡23)≈Θ(n1,585)T \in \Theta(n^{\log_2 3}) \approx \Theta(n^{1{,}585}). Für n=1024n = 1024 Ziffern sind das 310=59 0493^{10} = 59\,049 statt 410=1 048 5764^{10} = 1\,048\,576 Ziffernprodukte. (Dabei nehmen wir vereinfachend an, dass x1+x0x_1 + x_0 und y1+y0y_1 + y_0 keine zusätzliche Stelle bekommen; das ändert die Größenordnung nicht.)

Beispiel

Strassen: Matrizen mit sieben statt acht Produkten

Zwei n×nn \times n-Matrizen multipliziert man üblicherweise mit n3n^3 Multiplikationen von Zahlen. Teilt man jede Matrix in vier Blöcke der Größe n2×n2\frac n2 \times \frac n2, so ist jeder Block des Ergebnisses eine Summe von zwei Blockprodukten, etwa C11=A11B11+A12B21C_{11} = A_{11} B_{11} + A_{12} B_{21}. Das sind 88 Blockprodukte und Additionen von n2×n2\frac n2 \times \frac n2-Blöcken, die Θ(n2)\Theta(n^2) kosten: T(n)=8 T(n/2)+n2T(n) = 8\,T(n/2) + n^2, mit p=3p = 3 nach Fall 1 wieder Θ(n3)\Theta(n^3).

Volker Strassen zeigte 1969, dass 77 geschickt gewählte Blockprodukte genügen, wenn man dafür 1818 Blockadditionen und -subtraktionen in Kauf nimmt:

T(n)=7 T(n/2)+Θ(n2),p=log⁡27≈2,807,T∈Θ(nlog⁡27)T(n) = 7\,T(n/2) + \Theta(n^2), \qquad p = \log_2 7 \approx 2{,}807, \qquad T \in \Theta(n^{\log_2 7})

Fall 1 gilt, weil n2∈O(n2,807−0,8)n^2 \in O(n^{2{,}807 - 0{,}8}). Die Formeln für die sieben Produkte brauchst du hier nicht. Wichtig ist das Muster: Bei Teile und herrsche lohnt es sich, die Zahl aa der Teilprobleme zu senken, auch wenn dafür mehr Arbeit f(n)f(n) anfällt, solange ff in Fall 1 bleibt.

Kurz geprüft

Für T(n)=8 T(n/2)+n2T(n) = 8\,T(n/2) + n^2 gilt T∈Θ(nk)T \in \Theta(n^k). Welche Zahl ist kk?

Beispiel

Wo das Theorem nicht greift

T(n)=2 T(n/2)+nlog⁡nT(n) = 2\,T(n/2) + n \log n. Hier ist p=1p = 1. Es ist f(n)=nlog⁡n∉Θ(n)f(n) = n \log n \notin \Theta(n) und erst recht nicht in O(n1−ε)O(n^{1-\varepsilon}), also weder Fall 2 noch Fall 1. Für Fall 3 bräuchte man nlog⁡n≥C n1+εn \log n \ge C\, n^{1+\varepsilon}, also log⁡n≥C nε\log n \ge C\, n^{\varepsilon} für alle großen nn. Das ist für jedes ε>0\varepsilon > 0 falsch, denn aus der Analysis ist bekannt, dass log⁡nnε→0\frac{\log n}{n^{\varepsilon}} \to 0. Die Rekurrenz fällt in die Lücke zwischen Fall 2 und Fall 3.

Der Rekursionsbaum hilft trotzdem. Sei n=2kn = 2^k und T(1)=0T(1) = 0. Ebene jj hat 2j2^j Knoten der Größe n/2jn/2^j, jeder kostet n2jlog⁡n2j=n2j(k−j)\frac{n}{2^j} \log \frac{n}{2^j} = \frac{n}{2^j}(k - j). Die Ebene kostet also n(k−j)n(k - j), und summiert über j=0,…,k−1j = 0, \dots, k - 1:

T(n)=n(k+(k−1)+⋯+1)=n⋅k(k+1)2∈Θ(nlog⁡2n)T(n) = n\bigl(k + (k-1) + \dots + 1\bigr) = n \cdot \frac{k(k+1)}{2} \in \Theta(n \log^2 n)

Dabei ist log⁡2n=(log⁡n)2\log^2 n = (\log n)^2. Probe: T(1024)=1024⋅10⋅112=56 320T(1024) = 1024 \cdot \frac{10 \cdot 11}{2} = 56\,320. Erweiterte Fassungen des Theorems decken diesen Fall ab: Ist f∈Θ(nplog⁡kn)f \in \Theta(n^p \log^k n) mit k≥0k \ge 0, dann ist T∈Θ(nplog⁡k+1n)T \in \Theta(n^p \log^{k+1} n).

T(n)=T(n−1)+nT(n) = T(n-1) + n. So verhält sich Quicksort, wenn das Pivot immer das kleinste Element ist. Das Problem schrumpft um 11, nicht um einen Faktor; es gibt kein konstantes bb. Abwickeln mit T(1)=1T(1) = 1 ergibt T(n)=n+(n−1)+⋯+1=n(n+1)2∈Θ(n2)T(n) = n + (n-1) + \dots + 1 = \frac{n(n+1)}{2} \in \Theta(n^2).

Ebenso wenig passt das Theorem auf T(n)=T(n/3)+T(2n/3)+nT(n) = T(n/3) + T(2n/3) + n (verschieden große Teilprobleme). Dort hilft wieder der Rekursionsbaum: Jede volle Ebene kostet nn, und es gibt Θ(log⁡n)\Theta(\log n) Ebenen, also Θ(nlog⁡n)\Theta(n \log n).

Häufige Fehler

Größer heißt nicht polynomiell größer

Bei T(n)=2 T(n/2)+nlog⁡nT(n) = 2\,T(n/2) + n \log n schließt man leicht: f(n)=nlog⁡nf(n) = n \log n wächst schneller als nlog⁡22=nn^{\log_2 2} = n, also Fall 3, und damit T∈Θ(nlog⁡n)T \in \Theta(n \log n).

Richtig ist

Fall 3 verlangt einen Abstand um einen Faktor nεn^{\varepsilon} mit ε>0\varepsilon > 0, nicht nur schnelleres Wachstum. log⁡n\log n ist für große nn kleiner als jede Potenz nεn^{\varepsilon}. Die richtige Lösung ist Θ(nlog⁡2n)\Theta(n \log^2 n). Ein zweiter häufiger Fehler: ff mit nn statt mit nlog⁡ban^{\log_b a} vergleichen. Bei T(n)=4 T(n/2)+nT(n) = 4\,T(n/2) + n ist die Vergleichsgröße n2n^2, und es liegt Fall 1 vor, nicht Fall 2. Und in Fall 3 gehört die Regularitätsbedingung zur Prüfung; für f(n)=ndf(n) = n^d ist sie automatisch erfüllt, für ungewöhnliche ff nicht unbedingt.

Zusammenfassung

  • Teile und herrsche mit aa Teilproblemen der Größe n/bn/b und Zusatzarbeit f(n)f(n) führt auf T(n)=a T(n/b)+f(n)T(n) = a\,T(n/b) + f(n).

  • Der Rekursionsbaum hat alog⁡bn=nlog⁡baa^{\log_b n} = n^{\log_b a} Blätter; p=log⁡bap = \log_b a ist der kritische Exponent.

  • Fall 1: ff polynomiell kleiner als npn^p, dann Θ(np)\Theta(n^p). Fall 2: f∈Θ(np)f \in \Theta(n^p), dann Θ(nplog⁡n)\Theta(n^p \log n). Fall 3: ff polynomiell größer und regulär, dann Θ(f)\Theta(f).

  • Die Fälle entsprechen einer wachsenden, konstanten oder fallenden geometrischen Reihe der Ebenenkosten.

  • Binäre Suche Θ(log⁡n)\Theta(\log n), Mergesort Θ(nlog⁡n)\Theta(n \log n), Karatsuba Θ(nlog⁡23)\Theta(n^{\log_2 3}), Strassen Θ(nlog⁡27)\Theta(n^{\log_2 7}).

  • Weniger Teilprobleme (aa kleiner) senken den Exponenten, auch wenn ff dafür etwas größer wird.

  • Nicht anwendbar zum Beispiel bei 2 T(n/2)+nlog⁡n2\,T(n/2) + n \log n (Lücke zwischen den Fällen, Lösung Θ(nlog⁡2n)\Theta(n \log^2 n)) und bei T(n−1)+nT(n-1) + n (kein fester Teilungsfaktor, Lösung Θ(n2)\Theta(n^2)).

Übungen

Aufgabe 1Multiple Choice

Löse T(n)=9 T(n/3)+nT(n) = 9\,T(n/3) + n mit dem Master-Theorem.

Aufgabe 2Numerisch

Wie groß ist der kritische Exponent p=log⁡bap = \log_b a für T(n)=2 T(n/4)+nT(n) = 2\,T(n/4) + \sqrt n? Gib die Zahl als Dezimalzahl an.

Aufgabe 3Multiple Choice

Auf welche Rekurrenz lässt sich das Master-Theorem nicht anwenden?

Aufgabe 4Numerisch

Karatsuba multipliziert zwei Zahlen mit je 88 Ziffern. Die Rekursion teilt so lange, bis nur noch einstellige Zahlen multipliziert werden, und jede Ebene erzeugt aus einem Produkt drei halb so lange. Wie viele Produkte einstelliger Zahlen entstehen? (Nimm an, dass die Summen x1+x0x_1 + x_0 keine zusätzliche Stelle bekommen.)

Aufgabe 5Freitext

Löse T(n)=3 T(n/2)+n2T(n) = 3\,T(n/2) + n^2 mit dem Master-Theorem. Gib den Fall an und prüfe alle Voraussetzungen, auch die Regularitätsbedingung.

Aufgabe 6Freitext

Sei T(1)=0T(1) = 0 und T(n)=2 T(n/2)+nlog⁡nT(n) = 2\,T(n/2) + n \log n für Zweierpotenzen n=2kn = 2^k. Beweise mit Induktion über kk, dass T(2k)=2k⋅k(k+1)2T(2^k) = 2^k \cdot \frac{k(k+1)}{2} gilt, und folgere T∈Θ(nlog⁡2n)T \in \Theta(n \log^2 n). Erkläre, warum das Master-Theorem in der Grundform hier nicht hilft.