Rekursion und Rekurrenzgleichungen
Lesen anpassen
Nach dieser Lektion kannst du
die Laufzeit eines rekursiven Algorithmus als Rekurrenzgleichung aufschreiben,
eine Rekurrenz durch Abwickeln und mit einem Rekursionsbaum lösen,
eine vermutete Lösung mit der Substitutionsmethode durch vollständige Induktion beweisen,
begründen, warum die naive Fibonacci-Rekursion exponentiell viele Aufrufe macht,
die Schranken , und auseinanderhalten.
Vorausgesetzt: Laufzeit messen: Operationen zählen und O-Notation
In der letzten Lektion hast du Laufzeiten bestimmt, indem du Schleifendurchläufe gezählt und mit Summen addiert hast. Viele wichtige Algorithmen haben aber keine Schleife, an der man die Arbeit ablesen kann. Sie lösen ein Problem, indem sie sich selbst für ein kleineres Teilproblem aufrufen. Mergesort, Quicksort und die binäre Suche arbeiten so.
Nimm die binäre Suche in einem sortierten Feld mit einer Million Einträgen. Sie schaut den mittleren Eintrag an und sucht dann nur noch in der linken oder in der rechten Hälfte weiter, mit demselben Verfahren. Wie viele Einträge sieht sie sich schlimmstenfalls an? Im Programmtext steht diese Zahl nirgends. Sie steckt in der Frage, wie oft sich die Funktion selbst aufruft.
Die Antwort dieser Lektion: Man schreibt die Laufzeit als Funktion der Eingabegröße und drückt durch Werte von an kleineren Stellen aus. So entsteht eine Rekurrenzgleichung, und für solche Gleichungen gibt es Lösungsverfahren.
Die binäre Suche halbiert bei jedem Schritt den Bereich, in dem sie noch sucht. Wie viele Einträge eines sortierten Feldes mit Einträgen sieht sie schlimmstenfalls an?
Rekursiver Algorithmus
Ein Algorithmus heißt rekursiv, wenn er sich selbst für eine kleinere Eingabe aufruft. Er besteht aus zwei Teilen:
- Basisfall (Rekursionsanfang): kleine Eingaben, die direkt gelöst werden, ohne Selbstaufruf.
- Rekursionsfall: Die Eingabe wird auf eine oder mehrere kleinere Eingaben zurückgeführt, für die sich der Algorithmus selbst aufruft.
Damit die Rekursion endet, muss jeder Selbstaufruf näher an den Basisfall heranführen, zum Beispiel weil kleiner wird. Das einfachste Beispiel ist die Fakultät mit , denn es gilt :
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 |
Der Aufruf ruft auf, dieser und dieser , den Basisfall. Dann werden die Ergebnisse rückwärts multipliziert: , , , .
Kein rekursiver Algorithmus in diesem Sinn ist eine Funktion , die ohne Basisfall aufruft. Sie endet nie, weil immer weiter fällt, auch unter .
Von der Funktion zur Rekurrenz: Fakultät
Von der Funktion zur Rekurrenz: Fakultät
Sei die Zahl der Grundoperationen, die für ausführt. Im Basisfall sind es konstant viele, sagen wir (ein Vergleich, eine Rückgabe). Im Rekursionsfall sind es ebenfalls konstant viele, sagen wir (Vergleich, Subtraktion, Multiplikation, Rückgabe), und dazu kommen die Kosten des Aufrufs . Die sind nach Definition :
Das ist eine Rekurrenzgleichung, kurz Rekurrenz: Sie legt durch Werte an kleineren Stellen fest, und der Anfangswert macht die Folge eindeutig. Gesucht ist eine geschlossene Form, also ein Term in , in dem nicht mehr vorkommt. Hier kostet jedes Absteigen von nach genau , und es gibt solche Schritte bis . Also ist : Die Fakultät braucht lineare Zeit.
Untere und genaue Schranken: und
sagt nur, dass höchstens so schnell wächst wie . Auch liegt in . Das ist wahr, aber zu grob. Für genaue Aussagen gibt es zwei weitere Zeichen. Seien und wie bisher Funktionen von den natürlichen Zahlen in die nichtnegativen reellen Zahlen.
- (gesprochen „Omega von “), wenn es und gibt mit für alle . Das ist eine untere Schranke.
- (gesprochen „Theta von “), wenn und gilt. Dann wachsen und bis auf konstante Faktoren gleich schnell.
Beispiel: , denn für ist . Die Fakultät braucht Schritte, wenn und positiv sind. Gegenbeispiel: , aber , denn hieße , und das gilt nicht für alle großen .
Binäre Suche: Rekurrenz aufstellen und abwickeln
Binäre Suche: Rekurrenz aufstellen und abwickeln
Das Feld ist aufsteigend sortiert. Gesucht ist der Wert zwischen den Stellen und . rundet ab; in Formeln schreiben wir dafür und für das Aufrunden .
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 | |
| 4 | 1 | |
| 5 | 1 | |
| 6 | 1 |
Der Bereich hat Einträge. Ohne den mittleren bleiben , links und rechts . Im schlechtesten Fall geht es im größeren Teil weiter. Sei die Zahl der angesehenen Einträge (Zeile 4) im schlechtesten Fall:
Abwickeln heißt: die Gleichung immer wieder in sich selbst einsetzen, bis ein Muster sichtbar wird. Für ist , und es folgt
Bei ist , und . Also ist . Für jedes gilt genau ; den Beweis führst du in den Übungen. Für sind das Einträge, und die binäre Suche liegt in .
Abwickeln liefert eine Vermutung. Ein Beweis ist es erst, wenn man das Muster, hier das „“, mit Induktion absichert.
Löse durch Abwickeln: und für . Wie groß ist ?
Rekursionsbaum
Mergesort (ausführlich im Kapitel über Sortieralgorithmen) sortiert ein Feld, indem es das Feld in zwei Hälften teilt, jede Hälfte rekursiv sortiert und die beiden sortierten Hälften in linearer Zeit zu einer sortierten Folge mischt. Rechnen wir das Mischen von Werten mit Kosten und ein Feld der Länge mit Kosten , so erhalten wir für Zweierpotenzen die Rekurrenz und .
Hier gibt es zwei Selbstaufrufe, das Abwickeln wird unübersichtlich. Ein Rekursionsbaum ordnet die Arbeit: Jeder Aufruf ist ein Knoten, seine Kinder sind die Aufrufe, die er selbst startet. An jeden Knoten schreibt man die Kosten, die der Aufruf selbst verursacht, ohne die seiner Kinder. Die Summe über alle Knoten ist . Man summiert ebenenweise: Ebene ist der erste Aufruf, Ebene sind seine Kinder, und so weiter.
Für :
| Ebene | Knoten | Größe je Knoten | Kosten je Knoten | Kosten der Ebene |
|---|---|---|---|---|
Zusammen . Allgemein hat Ebene genau Knoten der Größe und kostet . Die Ebenen bis kosten je , die letzte Ebene besteht aus Blättern mit Kosten . Vermutung: .
Wie groß ist für und ? Zähle die Ebenen des Rekursionsbaums.
Substitutionsmethode: die Vermutung beweisen
Substitutionsmethode: die Vermutung beweisen
Der Baum liefert eine Vermutung, aber das Aufsummieren war Anschauung. Die Substitutionsmethode macht daraus einen Beweis: Man vermutet eine Lösung und beweist sie mit vollständiger Induktion, indem man die Vermutung für die kleineren Werte in die Rekurrenz einsetzt (substituiert). Behauptung: Für alle und gilt .
Induktionsanfang , also : und .
Induktion mit statt mit einer festen Konstante
Induktion mit statt mit einer festen Konstante
Behauptung: Für gilt . „Beweis“: Angenommen, . Dann ist , und liegt in . Fertig?
Nein. Der Induktionsschritt muss dieselbe Aussage mit derselben Konstante zeigen. Sonst wächst die Konstante bei jedem Halbieren um , und nach Halbierungen ist sie keine Konstante mehr. Die Ungleichung gilt aber für kein . Die Behauptung ist auch falsch, die Lösung ist . Schreibe in Induktionsbeweisen deshalb nie , sondern eine Ungleichung mit einer benannten Konstante.
Mergesort
- Vergleiche
- 0
- Vertauschungen
- 0
- Schreibzugriffe
- 0
- V verglichen
- T getauscht oder geschrieben
- P Pivot
- • markiert
- Arbeitsbereich
- am Platz
Teilen, dann Mischen
mergesort(lo, hi):wenn lo ≥ hi: zurückmitte ← ⌊(lo + hi) / 2⌋mergesort(lo, mitte)mergesort(mitte + 1, hi)kopiere A[lo..hi] nach B[lo..hi]i ← lo; j ← mitte + 1für k von lo bis hi:wenn i > mitte: A[k] ← B[j]; j ← j + 1sonst wenn j > hi: A[k] ← B[i]; i ← i + 1sonst wenn B[j] < B[i]: A[k] ← B[j]; j ← j + 1sonst: A[k] ← B[i]; i ← i + 1
Laufzeit bei n Zahlen: bester Fall , im Mittel , schlechtester Fall .
Probier es aus
Naive Fibonacci-Rekursion
Naive Fibonacci-Rekursion
Die Fibonacci-Zahlen sind , und für , also Die Definition lässt sich wörtlich als Programm schreiben:
| Zeile | Einrückung | Anweisung |
|---|---|---|
| 1 | 0 | |
| 2 | 1 | |
| 3 | 1 |
Sei die Zahl der Aufrufe von , die insgesamt auslöst, sich selbst mitgezählt. Der Aufruf selbst zählt , dazu kommen alle Aufrufe der beiden Teilaufrufe:
Die ersten Werte sind . So ruft zweimal und dreimal auf: Dieselben Teilprobleme werden immer wieder neu berechnet. Für sind es schon Aufrufe, für über Millionen.
Die naive Fibonacci-Rekursion braucht exponentiell viele Aufrufe
Für alle gilt . Weil jeder Aufruf mindestens eine Grundoperation kostet (den Vergleich in Zeile 2), liegt die Laufzeit von in .
Beweisidee: Jeder Aufruf mit startet zwei Teilaufrufe, deren Argument um höchstens kleiner ist. Die Zahl der Aufrufe verdoppelt sich also mindestens alle zwei Stufen.
Zuerst ist monoton wachsend: , und für ist .
Untere Schranke mit starker Induktion: Für und ist . Für gilt die Aussage nach Voraussetzung für , und mit der Monotonie folgt .
Obere Schranke ebenso: und . Für ist nach Voraussetzung , weil .
Schließlich ist , also liegt und damit die Laufzeit in .
Warum ist so langsam, obwohl mit einer sehr ähnlichen Rekursion linear ist?
Zusammenfassung
Ein rekursiver Algorithmus hat einen Basisfall und einen Rekursionsfall, der auf kleinere Eingaben zurückführt.
Seine Laufzeit erfüllt eine Rekurrenz: = Summe der Kosten der Teilaufrufe plus die Arbeit des Aufrufs selbst, dazu ein Anfangswert.
ist eine untere Schranke, eine obere und untere zugleich; heißt: gleiches Wachstum bis auf Konstanten.
Abwickeln: die Rekurrenz in sich einsetzen, bis ein Muster entsteht. Binäre Suche: ergibt .
Rekursionsbaum: Kosten ebenenweise summieren. hat Ebenen mit je und Blätter: .
Substitutionsmethode: Vermutung mit Induktion beweisen, immer mit derselben benannten Konstante, nie mit im Induktionsschritt.
Die naive Fibonacci-Rekursion macht mindestens Aufrufe, weil sie dieselben Teilprobleme immer wieder löst.
Übungen
Wie viele Aufrufe von finden bei der Berechnung von statt, den ersten Aufruf mitgezählt?
Für die binäre Suche gilt und für . Berechne .
Ein Algorithmus sieht alle Einträge eines Feldes einmal an und ruft sich dann für das Feld ohne den letzten Eintrag auf. Also gilt und . In welcher Klasse liegt ?
Wie viele Aufrufe von löst in der naiven Rekursion insgesamt aus, den ersten Aufruf mitgezählt?
Für Zweierpotenzen sei und . (So zählt man die Aufrufe von Mergesort: ein Aufruf und die Aufrufe der beiden Hälften.) Bestimme die Lösung mit einem Rekursionsbaum und beweise sie mit der Substitutionsmethode.
Beweise: Für und gilt für alle .
Beweise für die Aufrufzahl der naiven Fibonacci-Rekursion (, ) die Formel für alle .