Diviser pour régner

La stratégie « diviser pour régner » décompose un problème en instances plus petites de même forme, les résout indépendamment, puis combine leurs résultats.

Trois obligations

1. Diviser : définir les sous-problèmes et montrer que leur taille diminue.
2. Régner : résoudre les cas de base et traiter récursivement chaque sous-problème.
3. Combiner : construire la solution du problème parent et comptabiliser son coût.

Une récurrence courante du temps d'exécution est

$$T(n)=aT(n/b)+f(n),$$

où $a$ est le nombre de sous-problèmes, chacun de taille proche de $n/b$, et $f(n)$ couvre le partitionnement et la combinaison. L'arbre de récursion, la substitution ou le théorème maître permettent de résoudre les récurrences appropriées ; des tailles irrégulières et des dépendances peuvent demander d'autres méthodes.

Schémas représentatifs

• Tri fusion : deux tris sur une moitié et une fusion linéaire, soit $\Theta(n\log n)$.
• Tri rapide : un partitionnement linéaire et des tailles de sous-problèmes dépendantes de l'entrée.
• Recherche binaire : un sous-problème de taille moitié et un travail de combinaison constant.
• Paire de points la plus proche et multiplication de Karatsuba : la stratégie de combinaison apporte l'amélioration essentielle par rapport à l'énumération directe.

Le simple fait de découper un algorithme ne l'améliore pas. Les solutions des sous-problèmes et leur combinaison doivent résoudre le problème d'origine, et la récurrence obtenue doit réellement fournir une meilleure borne.

Frontière avec la programmation dynamique

Les sous-problèmes de la division pour régner sont généralement indépendants. Un fort chevauchement répète le travail et suggère la mémoïsation ou la programmation dynamique. Inversement, les deux styles peuvent employer la récursion : la syntaxe ne détermine pas la technique de conception.

Des branches indépendantes peuvent s'exécuter en parallèle, mais l'accélération pratique est limitée par le chemin critique, le travail de combinaison, l'ordonnancement, les communications et le trafic mémoire.

Un argument de récurrence complet

Pour trier huit éléments par fusion, les tailles sont un segment de 8, deux de 4, quatre de 2, puis huit cas de base de 1. Chacun des trois niveaux de fusion traite huit éléments au total. Dans le modèle simplifié $T(1)=1$, $T(n)=2T(n/2)+n$, on obtient $T(2)=4$, $T(4)=12$, $T(8)=32$. Ce sont des unités de travail du modèle, pas des comparaisons exactes ni du temps mesuré.

Pour $n=2^k$, chaque niveau coûte $n$, il y a $k$ niveaux et $n$ feuilles : $T(n)=n\log_2 n+n$. La correction exige une induction distincte : les segments de taille zéro ou un sont triés ; si les deux résultats plus petits sont triés, prendre la plus petite tête produit une permutation triée de leur union. La diminution stricte des tailles prouve la terminaison. Ni la récurrence seule ni la terminaison seule ne prouvent la correction du résultat.

Quand appliquer le théorème maître

Pour $T(n)=aT(n/b)+f(n)$, avec constantes $a\geq1$, $b>1$, coût de combinaison non négatif et cas de base constants, comparez $f(n)$ à $n^p$, où $p=\log_b a$. Une forme courante donne :

• Si $f(n)=O(n^{p-\varepsilon})$ pour un $\varepsilon>0$, alors $T(n)=\Theta(n^p)$.
• Si $f(n)=\Theta(n^p)$, alors $T(n)=\Theta(n^p\log n)$.
• Si $f(n)=\Omega(n^{p+\varepsilon})$ pour un $\varepsilon>0$ et $a f(n/b)\leq c f(n)$ à partir d’un certain rang pour une constante $c<1$, alors $T(n)=\Theta(f(n))$.

Ces cas sont suffisants, pas exhaustifs. Le tri fusion relève du cas central ; la recherche binaire a $a=1$, $b=2$, $f(n)=\Theta(1)$ et donne $\Theta(\log n)$. Elle est aussi classée comme réduction pour régner puisqu’un seul sous-problème est résolu. Les pivots arbitraires du tri rapide ne donnent pas des branches de tailles égales fixes : appliquer directement ce théorème à son pire cas est invalide. Des branches indépendantes permettent le parallélisme, sans supprimer le coût de combinaison.

Source

• MIT OpenCourseWare : diviser pour régner

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.