Fiche à trous · Terminale · NSI

Le paradigme diviser pour régner

Complétez de mémoire, puis vérifiez avec la page de corrigé.

Couper un problème en deux ne le rend pas automatiquement plus facile. Si l'une des moitiés contient presque tout, ou si recoller les morceaux coûte aussi cher que résoudre le problème entier, on a fait beaucoup de travail pour rien. Le paradigme n'est efficace que sous conditions, et c'est de ces conditions qu'il s'agit.

Le principe

Règle

Piège

Considérer qu'un algorithme relevant de diviser pour régner est nécessairement plus efficace qu'une approche directe.

Vérifier les deux conditions avant d'annoncer la moindre complexité.

Trois exemples classiques

Propriété

Le tri rapide illustre exactement ce que les deux conditions signifient. Sa combinaison est gratuite — après partition, les deux parties sont déjà à leur place relative —, ce qui est un avantage sur le tri fusion. Mais l'équilibre des tailles dépend du pivot : bien choisi, O(n log n) en moyenne ; systématiquement mal choisi, O(n²). D'où les stratégies de choix de pivot, qui sont tout l'enjeu de son implémentation.

Calculer la complexité

Propriété

Concevoir un algorithme diviser pour régner

Mes sous-problèmes sont-ils de même nature que le problème initial ?
Sont-ils de tailles comparables ?
Le coût de la combinaison est-il inférieur à celui d'une résolution directe ?
Ai-je écrit un cas de base atteint à coup sûr ?
Ai-je posé la récurrence au lieu d'annoncer une complexité de mémoire ?
Ai-je vérifié le cas défavorable, et pas seulement le cas moyen ?

Corrigé · à détacher

Le paradigme diviser pour régner

1. Diviser pour régner décompose un problème en sous-problèmes de même nature mais de taille moindre, les résout — le plus souvent par récurrence —, puis combine les solutions partielles. Trois étapes, donc : diviser, régner, combiner. Le gain ne vient pas de la division en elle-même, mais du fait que la somme des coûts des sous-problèmes plus le coût de combinaison soit inférieure au coût direct.
2. $d i v i ser \cdot r \overset{e}{ˊ} g n er \cdot co mbin er$
3. Le paradigme ne fait gagner que sous deux conditions. Les sous-problèmes doivent être de tailles comparables : couper en deux moitiés égales fait chuter la profondeur à log n, couper en un élément et le reste ramène au parcours linéaire. Et l'étape de combinaison doit rester peu coûteuse : si recoller coûte autant que résoudre, le découpage n'apporte rien.
4. $t ai l l esco m p a r ab l es + co mbinai so nb o nma r c h \overset{e}{ˊ}$
5. La recherche dichotomique divise l'espace de recherche en deux et n'en garde qu'une moitié : il n'y a donc rien à combiner, d'où une complexité en O(log n). Le tri fusion divise en deux moitiés égales, trie chacune, puis fusionne en temps linéaire : la garantie de tailles égales et la combinaison bon marché donnent O(n log n) dans tous les cas. Le tri rapide partitionne autour d'un pivot, et les deux parties n'ont aucune raison d'être égales.
6. La complexité se calcule par une relation de récurrence : le coût pour une entrée de taille n s'exprime en fonction du coût des sous-problèmes et du coût de combinaison. L'équation de maître donne le résultat selon lequel des deux l'emporte. Trois cas : si la combinaison domine, elle fixe la complexité ; si les sous-problèmes dominent, ce sont eux ; et s'ils s'équilibrent, un facteur logarithmique apparaît — c'est le cas du tri fusion.
7. $co \overset{u}{^} t (n) = a \times co \overset{u}{^} t (n / b) + co mbinai so n (n)$
8. Identifier un découpage produisant des sous-problèmes de même nature que l'original.
9. Vérifier que les sous-problèmes sont de tailles comparables — sinon le gain disparaît.
10. Écrire le cas de base : la plus petite entrée, résolue sans découpage.
11. Écrire l'étape de combinaison et en estimer le coût.
12. Poser la relation de récurrence et conclure, plutôt que d'annoncer une complexité par reconnaissance de forme.