/ Algorithmen & Komplexität

Master-Theorem (Fall 3)

Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 3 (c > log_b(a)) dominiert der Kombinieren-Schritt: T(n) = O(n^c).

01 · Eingabe

Master-Theorem (Fall 3) berechnen

Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 3 (c > log_b(a)) dominiert der Kombinieren-Schritt: T(n) = O(n^c).

Lösen für

T = n^c

n Eingabegröße

c Exponent

Worum geht es?

Im Fall 3 des Master-Theorems ist c > log_b(a) — der Kombinieren-Schritt produziert mehr Arbeit als die Rekursion absteigend einsparen kann. Damit dominiert die oberste Ebene des Rekursionsbaums die Gesamtlaufzeit: T(n) = O(n^c).

Voraussetzung für die saubere Anwendung ist zusätzlich die Regularitätsbedingung a · f(n/b) ≤ k · f(n) für ein k < 1 — in der Praxis fast immer erfüllt.

Die Formel

Formel Master-Theorem Fall 3

Rekurrenz:  T(n) = a · T(n / b) + O(n^c)
Bedingung:  c > log_b(a)

T = n^c

Umstellungen:
    n = T^(1 / c)
    c = log_n(T)

Die Variablen

Symbol	Bedeutung	Einheit	Erklärung
n	Eingabegröße	—	Größe der Eingabe (n > 0, n ≠ 1).
c	Exponent	—	Exponent des nicht-rekursiven Anteils.
T	Laufzeit	—	Asymptotische Gesamtlaufzeit.

Minimal-Beispiel

a = 2, b = 2, c = 2. log₂(2) = 1 < 2 → Fall 3. Für n = 100:

Rechnung Quadratisch dominiert

T = 100²
  = 10 000

Praxis-Beispiele

Beispiel 1 — Naive Matrizenmultiplikation rekursiv

a = 8, b = 2, c = 3. log₂(8) = 3 = c → Fall 2, nicht Fall 3. Ändert man c auf 3,5, gilt 3,5 > 3 → Fall 3 → T(n) = n^3,5.

Rechnung Hypothetisch

T(n) = n^3,5

Beispiel 2 — Eingabegröße rückwärts bestimmen

T = 1 000 000 Ops bei c = 2:

Rechnung Eingabegröße

n = T^(1 / c)
  = 1 000 000^0,5
  = 1000

Beispiel 3 — Exponent c aus Messung

Für n = 100 misst Du T = 10 000 000:

Rechnung Exponent

c = log₁₀₀(10 000 000)
  = log(10⁷) / log(100)
  = 7 / 2
  = 3,5