Master-Theorem (Fall 1)
Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 1 (c < log_b(a)) dominiert die Rekursion: T(n) = O(n^(log_b(a))).
Master-Theorem (Fall 1) berechnen
Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 1 (c < log_b(a)) dominiert die Rekursion: T(n) = O(n^(log_b(a))).
Worum geht es?
Das Master-Theorem löst Rekurrenzen der Form T(n) = a · T(n/b) + O(n^c), die bei Divide-&-Conquer-Algorithmen auftreten. Es vergleicht den Exponenten c des Kombinieren-Schritts mit log_b(a), dem „kritischen Exponenten" der Rekursion.
Im Fall 1 ist c < log_b(a) — die Rekursion produziert mehr Arbeit als der Kombinieren-Schritt aufwiegen kann. Das Ergebnis: T(n) = O(n^(log_b(a))).
Die Formel
Rekurrenz: T(n) = a · T(n / b) + O(n^c)
Bedingung: c < log_b(a)
T = n^(log_b(a))Die Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| n | Eingabegröße | — | Größe der Eingabe (n > 0). |
| a | Rekursionsanzahl | — | Anzahl rekursiver Aufrufe pro Ebene. |
| b | Teilungsfaktor | — | Teilungsfaktor pro Aufruf (b > 1). |
| T | Laufzeit | — | Asymptotische Gesamtlaufzeit. |
Minimal-Beispiel
Algorithmus mit a = 4 rekursiven Aufrufen auf halbierten Teilen (b = 2), linearer Kombinieren-Aufwand (c = 1):
log₂(4) = 2 → c = 1 < 2 → Fall 1
T(n) = n^2Praxis-Beispiele
Beispiel 1 — Karatsuba-Multiplikation
a = 3, b = 2, c = 1 (lineare Kombination):
log₂(3) ≈ 1,585 → c = 1 < 1,585 → Fall 1
T(n) ≈ n^1,585Beispiel 2 — Strassen-Matrizenmultiplikation
a = 7, b = 2, c = 2 (n²-Kombination):
log₂(7) ≈ 2,807 → c = 2 < 2,807 → Fall 1
T(n) ≈ n^2,807Beispiel 3 — Konkreter Laufzeitwert
Für n = 1024, a = 4, b = 2, c = 0:
Exponent = log₂(4) = 2
T(1024) = 1024²
= 1 048 576