Master Theorem
Der Hauptsatz (Master-Theorem) gibt die asymptotische Schranke der Teile-und-Herrsche-Rekurrenz T(n)=aT(n/b)+f(n) in drei Fällen, die f mit n^(log_b a) vergleichen.
Zweck
Schnelle Analyse der Teile-und-Herrsche-Komplexität ohne Ausmultiplizieren der Rekurrenz.
Mechanismus
Sei c=log_b a. Fall 1: f=O(n^(c-ε)) → T=Θ(n^c). Fall 2: f=Θ(n^c log^k n) → T=Θ(n^c log^(k+1) n). Fall 3: f=Ω(n^(c+ε)) plus Regularitätsbedingung → T=Θ(f).
Anwendungsfälle
- Komplexitätsanalyse
- Teile-und-Herrsche-Algorithmen
- Lösung von Rekurrenzen