Divide and Conquer
Diviser pour régner scinde un problème en sous-problèmes indépendants, les résout récursivement et fusionne les résultats ; le théorème maître analyse généralement sa complexité.
Objectif
Fournir un paradigme général de conception d'algorithmes efficaces, comme le tri fusion ou la transformée de Fourier rapide.
Mécanisme
Trois étapes : diviser (scinder en sous-problèmes), régner (résoudre récursivement), combiner (fusionner les sous-solutions). Théorème maître : borne asymptotique de T(n)=aT(n/b)+f(n). Classiques : tri fusion O(n log n), FFT O(n log n).
Cas d’usage
- Conception d'algorithmes
- Tri et recherche
- Multiplication de polynômes