Das Master-Theorem
Lesen anpassen
Nach dieser Lektion kannst du
eine Teile-und-herrsche-Rekurrenz 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 Ziffern multiplizierst du in der Schule, indem du jede Ziffer der einen mit jeder Ziffer der anderen malnimmst. Das sind 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 Ziffern: und . Ausmultiplizieren ergibt . Das sind vier Produkte von Zahlen mit Ziffern, dazu Additionen und Verschiebungen um Zehnerstellen, die zusammen linear viel kosten. Für die Laufzeit gilt also , wenn wir die lineare Arbeit mit Kosten 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.
Für die Multiplikation mit vier halb so großen Teilprodukten gilt und . Wie schnell wächst ?
Teile-und-herrsche-Rekurrenz
Ein Verfahren, das ein Problem der Größe in Teilprobleme der Größe zerlegt, sie rekursiv löst und dafür außerhalb der Aufrufe die Arbeit leistet (Teilen und Zusammensetzen), hat die Laufzeit
.
Dabei sind und Konstanten, , und ist für kleine eine positive Konstante. Ist keine ganze Zahl, wird auf- oder abgerundet; das ändert das Ergebnis des Satzes unten nicht.
| Verfahren | |||
|---|---|---|---|
| binäre Suche | |||
| Mergesort | |||
| Multiplikation mit vier Teilprodukten |
Keine Rekurrenz dieser Form ist : Das Problem wird um kleiner, nicht um einen festen Faktor . Ebenso wenig , denn die Zahl der Teilprobleme ist keine Konstante.
Der Rekursionsbaum allgemein
Der Rekursionsbaum allgemein
Sei eine Potenz von , also mit , und sei .
Auf Ebene liegen Knoten, denn jeder Knoten hat Kinder. Jeder hat die Größe und kostet selbst .
Master-Theorem
Seien und Konstanten, , und erfülle für alle großen (mit auf- oder abgerundet), wobei für kleine eine positive Konstante ist. Sei .
- Fall 1: Gibt es ein mit , so ist . Die Blätter dominieren.
- Fall 2: Ist , so ist . Alle Ebenen kosten etwa gleich viel.
- Fall 3: Gibt es ein mit und eine Konstante mit für alle großen (Regularitätsbedingung), so ist . Die Wurzel dominiert.
In Fall 1 und 3 muss also um einen Faktor kleiner beziehungsweise größer sein als , nicht nur irgendwie kleiner oder größer.
Wir beweisen den wichtigsten Spezialfall mit einer Konstante , für und . Beweisidee: Die Ebenenkosten bilden eine geometrische Reihe, und es kommt nur darauf an, ob ihr Quotient kleiner, gleich oder größer als ist.
Ebene kostet mit . Also ist . Es gilt , ebenso und .
(Fall 3): Die Reihe liegt zwischen ihrem ersten Glied und . Also ist , und weil , ist . Die Regularität gilt hier von selbst: .
(Fall 2): Jede der Ebenen kostet , also .
(Fall 1): Die Reihe ist . Es ist . Also , das heißt .
Für allgemeines schätzt man genauso ab: In Fall 1 ist , das gibt eine wachsende geometrische Reihe mit Quotient . In Fall 3 liefert die Regularität , eine fallende geometrische Reihe. Dass Runden von nichts ändert, zeigt man mit etwas mehr Rechenaufwand; das lassen wir hier weg.
Binäre Suche und Mergesort
Binäre Suche und Mergesort
Binäre Suche: . Hier ist , , , und . Fall 2 liefert , wie in der letzten Lektion durch Abwickeln.
Mergesort: . Hier ist und . Wieder Fall 2:
In beiden Fällen kostet jede Ebene des Rekursionsbaums gleich viel ( beziehungsweise ), und es gibt Ebenen. Das ist die Anschauung von Fall 2.
Welcher Fall des Master-Theorems liegt bei vor?
Karatsuba: drei statt vier Teilprodukte
Karatsuba: drei statt vier Teilprodukte
Die Multiplikation mit vier Teilprodukten aus der Einleitung ist nach Fall 1 in : und . Anatoli Karatsuba fand 1960 einen Trick: Der mittlere Koeffizient lässt sich aus einem weiteren Produkt gewinnen, denn . Man braucht also nur , und :
Beispiel mit : , , , Mittelteil . Ergebnis .
Die zusätzlichen Additionen kosten nur linear viel, also . Nun ist und . Fall 1 ergibt . Für Ziffern sind das statt Ziffernprodukte. (Dabei nehmen wir vereinfachend an, dass und keine zusätzliche Stelle bekommen; das ändert die Größenordnung nicht.)
Strassen: Matrizen mit sieben statt acht Produkten
Strassen: Matrizen mit sieben statt acht Produkten
Zwei -Matrizen multipliziert man üblicherweise mit Multiplikationen von Zahlen. Teilt man jede Matrix in vier Blöcke der Größe , so ist jeder Block des Ergebnisses eine Summe von zwei Blockprodukten, etwa . Das sind Blockprodukte und Additionen von -Blöcken, die kosten: , mit nach Fall 1 wieder .
Volker Strassen zeigte 1969, dass geschickt gewählte Blockprodukte genügen, wenn man dafür Blockadditionen und -subtraktionen in Kauf nimmt:
Fall 1 gilt, weil . Die Formeln für die sieben Produkte brauchst du hier nicht. Wichtig ist das Muster: Bei Teile und herrsche lohnt es sich, die Zahl der Teilprobleme zu senken, auch wenn dafür mehr Arbeit anfällt, solange in Fall 1 bleibt.
Für gilt . Welche Zahl ist ?
Wo das Theorem nicht greift
Wo das Theorem nicht greift
. Hier ist . Es ist und erst recht nicht in , also weder Fall 2 noch Fall 1. Für Fall 3 bräuchte man , also für alle großen . Das ist für jedes falsch, denn aus der Analysis ist bekannt, dass . Die Rekurrenz fällt in die Lücke zwischen Fall 2 und Fall 3.
Der Rekursionsbaum hilft trotzdem. Sei und . Ebene hat Knoten der Größe , jeder kostet . Die Ebene kostet also , und summiert über :
Dabei ist . Probe: . Erweiterte Fassungen des Theorems decken diesen Fall ab: Ist mit , dann ist .
. So verhält sich Quicksort, wenn das Pivot immer das kleinste Element ist. Das Problem schrumpft um , nicht um einen Faktor; es gibt kein konstantes . Abwickeln mit ergibt .
Ebenso wenig passt das Theorem auf (verschieden große Teilprobleme). Dort hilft wieder der Rekursionsbaum: Jede volle Ebene kostet , und es gibt Ebenen, also .
Größer heißt nicht polynomiell größer
Größer heißt nicht polynomiell größer
Bei schließt man leicht: wächst schneller als , also Fall 3, und damit .
Fall 3 verlangt einen Abstand um einen Faktor mit , nicht nur schnelleres Wachstum. ist für große kleiner als jede Potenz . Die richtige Lösung ist . Ein zweiter häufiger Fehler: mit statt mit vergleichen. Bei ist die Vergleichsgröße , und es liegt Fall 1 vor, nicht Fall 2. Und in Fall 3 gehört die Regularitätsbedingung zur Prüfung; für ist sie automatisch erfüllt, für ungewöhnliche nicht unbedingt.
Zusammenfassung
Teile und herrsche mit Teilproblemen der Größe und Zusatzarbeit führt auf .
Der Rekursionsbaum hat Blätter; ist der kritische Exponent.
Fall 1: polynomiell kleiner als , dann . Fall 2: , dann . Fall 3: polynomiell größer und regulär, dann .
Die Fälle entsprechen einer wachsenden, konstanten oder fallenden geometrischen Reihe der Ebenenkosten.
Binäre Suche , Mergesort , Karatsuba , Strassen .
Weniger Teilprobleme ( kleiner) senken den Exponenten, auch wenn dafür etwas größer wird.
Nicht anwendbar zum Beispiel bei (Lücke zwischen den Fällen, Lösung ) und bei (kein fester Teilungsfaktor, Lösung ).
Übungen
Löse mit dem Master-Theorem.
Wie groß ist der kritische Exponent für ? Gib die Zahl als Dezimalzahl an.
Auf welche Rekurrenz lässt sich das Master-Theorem nicht anwenden?
Karatsuba multipliziert zwei Zahlen mit je 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 keine zusätzliche Stelle bekommen.)
Löse mit dem Master-Theorem. Gib den Fall an und prüfe alle Voraussetzungen, auch die Regularitätsbedingung.
Sei und für Zweierpotenzen . Beweise mit Induktion über , dass gilt, und folgere . Erkläre, warum das Master-Theorem in der Grundform hier nicht hilft.