/ Algorithmen & Komplexität

Master-Theorem (Fall 2)

Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 2 (c = log_b(a)) tragen Rekursion und Kombinieren gleich bei: T(n) = O(n^c · log n).

01 · Eingabe

Master-Theorem (Fall 2) berechnen

Rekurrenz T(n) = a·T(n/b) + O(n^c). Im Fall 2 (c = log_b(a)) tragen Rekursion und Kombinieren gleich bei: T(n) = O(n^c · log n).

T = n^c · log₂(n)

n Eingabegröße

c Exponent

Worum geht es?

Im Fall 2 des Master-Theorems ist c = log_b(a) — der nicht-rekursive Aufwand und der Rekursionsbeitrag sind asymptotisch gleich groß. Beide tragen auf jeder der log_b(n) vielen Ebenen denselben Aufwand bei, was den zusätzlichen Logarithmus-Faktor erzeugt.

Klassisches Beispiel: Merge Sort mit a = 2, b = 2, c = 1 — also log_b(a) = 1 = c → Fall 2 → T(n) = O(n · log n).

Die Formel

Formel Master-Theorem Fall 2

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

T = n^c · log₂(n)

Die Variablen

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

Minimal-Beispiel

Merge Sort: c = 1, n = 1024.

Rechnung Merge Sort

T = 1024^1 · log₂(1024)
  = 1024 · 10
  = 10 240

Praxis-Beispiele

Beispiel 1 — Binäre Suche

a = 1, b = 2, c = 0. log₂(1) = 0 = c → Fall 2.

Rechnung Binäre Suche

T = n^0 · log₂(n)
  = log₂(n)

Beispiel 2 — Matrizenmultiplikation mit a = 4, b = 2, c = 2

log₂(4) = 2 = c → Fall 2.

Rechnung n² log n

T(n) = n² · log₂(n)

Für n = 1000:
    T = 10⁶ · log₂(1000)
      ≈ 10⁶ · 10
      ≈ 10⁷

Beispiel 3 — Vergleich zu O(n²)

n = 10⁶:

Rechnung Vergleich

O(n log n) ≈ 10⁶ · 20  ≈ 2 · 10⁷
O(n²)      =          10¹²

Faktor: 50 000-fach.