Rekursionsgleichungen

Rekursionsgleichungen drücken die Laufzeit eines rekursiven Algorithmus in Abhängigkeit von seiner Laufzeit bei kleineren Eingaben aus; ihre Lösung liefert die geschlossenen asymptotischen Schranken, die zur Analyse von Divide-and-Conquer- und anderen rekursiven Algorithmen verwendet werden.

Definition

Eine Rekursionsgleichung ist eine Gleichung, die den Wert einer Funktion bei einer Eingabe in Abhängigkeit von ihren Werten bei kleineren Eingaben definiert; in der Algorithmenanalyse drückt sie die Kosten eines Algorithmus für eine Eingabe der Größe n in Abhängigkeit von seinen Kosten für kleinere Teilprobleme aus.

Scope

Dieses Thema behandelt die Formulierung und Lösung von Rekursionen, die in der Algorithmenanalyse auftreten: die Substitutionsmethode, die Rekursionsbaum-Methode und das Master-Theorem für Divide-and-Conquer-Rekursionen der Form T(n) = aT(n/b) + f(n). Es erklärt, wie jeder rekursive Algorithmus eine Rekursion induziert und wie diese Rekursion in eine Big-Theta-Schranke übersetzt wird. Es schließt die asymptotische Notation selbst aus, die separat behandelt wird, sowie kombinatorische erzeugende Funktionen aus der diskreten Mathematik.

Core questions

• Wie führt ein rekursiver Algorithmus zu einer Rekursionsgleichung für seine Laufzeit?
• Wie wird die Substitutionsmethode verwendet, um eine vermutete Lösung zu beweisen und zu verifizieren?
• Wie deckt die Rekursionsbaum-Methode die gesamte Arbeit über Rekursionsebenen hinweg auf?
• Wann ist das Master-Theorem anwendbar und was bedeuten seine drei Fälle?
• Wie werden Rekursionen behandelt, die außerhalb der Form des Master-Theorems liegen?

Key concepts

• Rekursionsgleichung
• Substitutionsmethode
• Rekursionsbaum-Methode
• Master-Theorem
• Divide-and-Conquer-Rekursion
• Basisfall und rekursiver Fall
• geschlossene Lösung
• Akra-Bazzi-Methode

Key theories

Master-Theorem

Für Divide-and-Conquer-Rekursionen T(n) = aT(n/b) + f(n) liefert das Master-Theorem die asymptotische Lösung, indem es f(n) mit n hoch dem Logarithmus zur Basis b von a vergleicht, wobei die drei Fälle abgedeckt werden, in denen die Blätter, die Wurzel oder ausgeglichene Ebenen dominieren.

Rekursionsbaum- und Substitutionsmethoden

Die Rekursionsbaum-Methode summiert die auf jeder Rekursionsebene geleistete Arbeit, um eine Schranke vorzuschlagen, die die Substitutionsmethode dann induktiv rigoros beweist; zusammen behandeln sie Rekursionen, die über den Anwendungsbereich des Master-Theorems hinausgehen.

Clinical relevance

Die Lösung von Rekursionsgleichungen ist der Standardweg zur Bestimmung der Laufzeit rekursiver Algorithmen, von Mergesort und Quicksort bis hin zur schnellen Multiplikation und vielen dynamischen Programmen. Ingenieure und Forscher verwenden das Master-Theorem routinemäßig, um die asymptotischen Komplexitätsaussagen solcher Algorithmen abzuleiten und zu begründen.

History

Die Rekursionsanalyse von Algorithmen wurde in Knuths „The Art of Computer Programming“ systematisiert. Das Master-Theorem wurde durch CLRS zu einem Lehrbuchstandard, und die Akra-Bazzi-Methode (1998) verallgemeinerte es auf eine breitere Klasse von Divide-and-Conquer-Rekursionen mit ungleichmäßigen Aufteilungen.

Key figures

• Donald Knuth
• Mohamad Akra
• Louay Bazzi

Seminal works

• cormen2009
• knuth1997vol1

Frequently asked questions

Wann kann ich das Master-Theorem verwenden?

Das Master-Theorem gilt für Rekursionen der Form T(n) = aT(n/b) + f(n) mit a >= 1 und b > 1, wobei jede Ebene das Problem in a Teilprobleme der Größe n/b aufteilt. Rekursionen mit ungleichmäßigen Aufteilungen, variierenden Teilproblemgrößen oder nicht-polynomiellen Kombinationskosten erfordern möglicherweise stattdessen die Rekursionsbaum-, Substitutions- oder Akra-Bazzi-Methoden.

Warum ergibt Mergesorts Rekursion O(n log n)?

Mergesort ergibt T(n) = 2T(n/2) + O(n): zwei halb so große Teilprobleme plus lineares Zusammenführen. Hier ist die Arbeit pro Ebene über alle log n Ebenen des Rekursionsbaums gleich, sodass die Gesamtsumme n mal log n beträgt, was das Master-Theorem als Theta(n log n) bestätigt.