Master-Theorem

Zweck und Grundidee

Das Master-Theorem (Hauptsatz der Laufzeitfunktionen) ist ein Spezialfall des Akra-Bazzi-Theorems. Es liefert schnell eine asymptotische Laufzeitklasse für bestimmte rekursiv definierte Funktionen. Es ist wichtig für die Analyse rekursiver Algorithmen, weil es den Aufwand der Teilprobleme mit dem Aufwand außerhalb der Rekursion vergleicht.

Es ist jedoch nicht auf jede Rekurrenz anwendbar. Passt keiner seiner Fälle, muss die Komplexitätsklasse mit anderen Methoden bestimmt werden.

Standardform und die drei Fälle

Die Standardform lautet:

T(n) = a · T(n/b) + f(n).

T(n) ist die gesuchte Laufzeitfunktion. Dabei ist a ≥ 1 die Anzahl der Unterprobleme, 1/b mit b > 1 der Anteil des ursprünglichen Problems pro Unterproblem und f(n) eine von T unabhängige, nicht negative Funktion. f(n) beschreibt die Kosten für das Aufteilen des Problems und das Zusammenführen der Teillösungen.

Entscheidend ist der Vergleich von f(n) mit n^(log_b a):

• Erster Fall: Gilt f(n) ∈ O(n^(log_b a − ε)) für ein ε > 0, dann T(n) ∈ Θ(n^(log_b a)). Die Rekursion selbst bestimmt also den Aufwand.
• Zweiter Fall: Gilt f(n) ∈ Θ(n^(log_b a)), dann T(n) ∈ Θ(n^(log_b a) log(n)). Rekursion und zusätzlicher Aufwand sind gleich stark.
• Dritter Fall: Gilt f(n) ∈ Ω(n^(log_b a + ε)) für ein ε > 0 und außerdem für ein c mit 0 < c < 1 sowie alle hinreichend großen n: a f(n/b) ≤ c f(n), dann T(n) ∈ Θ(f(n)). Hier dominiert der zusätzliche Aufwand f(n).

Höchstens einer dieser Fälle kann passen.

Anwendung der drei Fälle

Für T(n) = 8T(n/2) + 1000n² gilt a = 8, b = 2 und log₂8 = 3. Da 1000n² ∈ O(n^(3 − ε)) mit ε = 1, liegt der erste Fall vor. Daher gilt T(n) ∈ Θ(n³).

Für T(n) = 2T(n/2) + 10n gilt log₂2 = 1 und 10n ∈ Θ(n). Dies ist der zweite Fall; somit T(n) ∈ Θ(n log(n)).

Für T(n) = 2T(n/2) + n² gilt ebenfalls log₂2 = 1. n² ∈ Ω(n^(1 + ε)) mit ε = 1. Die Zusatzbedingung des dritten Falls ist erfüllt, denn 2(n/2)² = 1/2 n² ≤ c n² mit c = 1/2. Folglich gilt T(n) ∈ Θ(n²).

Verallgemeinerung und Hinweise

Die Rekurrenz T(n) = 8T(n/2) + n³ ln(n) ist nicht direkt durch die drei Grundfälle lösbar. Zwar sind a = 8, b = 2 und log₂8 = 3, aber n³ ln(n) gehört für kein ε > 0 zu Ω(n^(3 + ε)), weil ln(n)/n^ε gegen 0 geht. Der dritte Fall gilt daher nicht.

Eine Verallgemeinerung des zweiten Falls lautet: Falls f(n) ∈ Θ(n^(log_b a) ln^k n), dann gilt T(n) ∈ Θ(n^(log_b a) ln^(k+1) n). Für f(n) = n³ ln(n) ist k = 1; daher gilt T(n) ∈ Θ(n³ ln²(n)).

Floor- und Ceiling-Ausdrücke wie T(n) = aT(⌊n/b⌋) + f(n) können mithilfe von n/b abgeschätzt werden. Außerdem spielt die Basis eines Logarithmus in einer Θ-Abschätzung keine Rolle: ln(n) und lg(n) unterscheiden sich nur um einen konstanten Faktor.

Allgemeinere Rekurrenzen und Mergesort

Eine allgemeinere Form ist T(n) = Σ(i=1 bis m) T(α_i n) + f(n), wobei 0 < α_i < 1, m ≥ 1 und f(n) ∈ Θ(n^k) mit k ∈ ℕ₀. Für reelle Argumente wird T durch T(x) := T(⌊x⌋) oder T(⌈x⌉) fortgesetzt.

Dann gilt:

• Ist Σ α_i^k < 1, so T(n) ∈ Θ(n^k).
• Ist Σ α_i^k = 1, so T(n) ∈ Θ(n^k log n).
• Ist Σ α_i^k > 1, so T(n) ∈ Θ(n^c), wobei c durch Σ α_i^c = 1 bestimmt ist.

Mergesort erfüllt T(n) = 2T(n/2) + c · n. Mit a = 2, b = 2 und f(n) = c · n ist log₂2 = 1; daher gilt nach dem zweiten Fall T(n) ∈ Θ(n · log(n)).