Master Theorem
Le théorème maître donne la borne asymptotique de la récurrence diviser-pour-régner T(n)=aT(n/b)+f(n) en trois cas comparant f à n^(log_b a).
Objectif
Analyser rapidement la complexité diviser-pour-régner sans développer la récurrence.
Mécanisme
Soit c=log_b a. Cas 1 : f=O(n^(c-ε)) → T=Θ(n^c). Cas 2 : f=Θ(n^c log^k n) → T=Θ(n^c log^(k+1) n). Cas 3 : f=Ω(n^(c+ε)) plus la condition de régularité → T=Θ(f).
Cas d’usage
- Analyse de complexité
- Algorithmes diviser-pour-régner
- Résolution de récurrences