Programme en vigueur — arrêtés du 19 juillet 2019, applicable en Terminale depuis la rentrée 2020. Voir le texte
Principe : décomposer le problème, résoudre les sous-problèmes, combiner. Exemples : tri fusion, tri rapide, recherche dichotomique. Complexité par récurrence : équation de maître.
La règle d'or
Diviser pour régner ne fait gagner que si les sous-problèmes sont de tailles comparables et si l'étape de combinaison reste peu coûteuse.
L'erreur que tout le monde fait
Considérer qu'un algorithme relevant de diviser pour régner est nécessairement plus efficace qu'une approche directe.
Le gain vient du découpage équilibré : si un pivot mal choisi sépare un élément d'un côté et tout le reste de l'autre, la récursion se déroule sur presque toute la taille à chaque étape et le coût rejoint celui d'un tri élémentaire. À l'inverse, un découpage équilibré mais suivi d'une combinaison coûteuse annule aussi le bénéfice.
Examiner deux points avant de conclure : l'équilibre du découpage dans le pire cas, et le coût de la combinaison.
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.
1Le principe
Règle
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.
diviser⋅reˊgner⋅combiner
Règle
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.
taillescomparables+combinaisonbonmarcheˊ
Piège
Considérer qu'un algorithme relevant de diviser pour régner est nécessairement plus efficace qu'une approche directe.
Pourquoi — Le paradigme est une méthode de conception, pas une garantie de performance. Un découpage déséquilibré annule le gain : le tri rapide mal pivoté dégénère en O(n²), exactement comme un tri élémentaire. Et une combinaison coûteuse peut absorber tout le bénéfice. Annoncer une complexité parce qu'on reconnaît le paradigme, c'est confondre la forme de l'algorithme et son coût.
Le réflexe — Vérifier les deux conditions avant d'annoncer la moindre complexité.
2Trois exemples classiques
Propriété
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.
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.
3Calculer la complexité
Propriété
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.
cou^t(n)=a×cou^t(n/b)+combinaison(n)
Concevoir un algorithme diviser pour régner
Identifier un découpage produisant des sous-problèmes de même nature que l'original.
Vérifier que les sous-problèmes sont de tailles comparables — sinon le gain disparaît.
Écrire le cas de base : la plus petite entrée, résolue sans découpage.
Écrire l'étape de combinaison et en estimer le coût.1000000÷20000=50Sur un million d'éléments, n log n vaut environ 20 millions contre 10¹² pour n² : le rapport dépasse 50 000.
Poser la relation de récurrence et conclure, plutôt que d'annoncer une complexité par reconnaissance de forme.
▢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 ?
L'essentiel en 11 points
·Diviser pour régner : diviser, régner, combiner.
·Deux conditions : sous-problèmes de tailles comparables, combinaison bon marché.
·Le paradigme est une méthode de conception, pas une garantie de performance.
·Dichotomie : une seule moitié gardée, donc rien à combiner — O(log n).
·Tri fusion : moitiés égales par construction, O(n log n) dans tous les cas.
·Il coûte de la mémoire supplémentaire : il n'opère pas sur place.
·Tri rapide : combinaison gratuite, mais équilibre dépendant du pivot.
·Mal pivoté systématiquement, il dégénère en O(n²).
·La complexité se calcule par une récurrence, pas par reconnaissance de forme.
·L'équation de maître tranche selon ce qui domine : sous-problèmes ou combinaison.
·Aucun tri ne l'emporte dans l'absolu : garantie contre performance moyenne.
2
Imprimer
Fiche PDF — Paradigme diviser pour régner
Gratuit · sans compte
Trois documents à imprimer, 6 pages en tout : le cours, les exercices avec la place pour écrire, et le corrigé détaillé avec son barème.
c.Pourquoi la dichotomie n'a-t-elle pas d'étape de combinaison ?
d.Quelle est la complexité du tri fusion ? Dans quels cas ?
e.De quoi dépend la complexité du tri rapide ?
›Voir le corrigéMasquer le corrigé
a. Diviser, régner, combiner.
b. Des sous-problèmes de tailles comparables, et une combinaison peu coûteuse.
c. Parce qu'elle ne garde qu'une des deux moitiés : il n'y a pas deux résultats à recoller.
d. O(n log n), dans tous les cas — les moitiés sont égales par construction.
e. Du choix du pivot : bien choisi, O(n log n) en moyenne ; systématiquement mal choisi, O(n²).
2
Comparer les ordres de grandeur pour n = 1 000 000. On prendra log n ≈ 20.
Calculer
a.Calculer n log n.
b.Calculer n², en ordre de grandeur.
c.Calculer le rapport entre les deux.
d.Que signifie ce rapport en pratique ?
›Voir le corrigéMasquer le corrigé
a. Produit :1000000×20=20000000
Soit 20 millions d'opérations.
b. Carré :1000000×1000000=1000000000000
Soit mille milliards.
c. Rapport :1000000000000÷20000000=50000
Soit cinquante mille fois plus d'opérations.
d. Que l'un des deux termine en une fraction de seconde et l'autre en des heures — sur la même machine. Aucun processeur plus rapide ne comble un écart de cet ordre : c'est la loi de croissance qui décide, pas le matériel.
3
Un développeur affirme que son algorithme est rapide « parce qu'il applique diviser pour régner ». Discuter.
Argumenter
a.L'appartenance au paradigme garantit-elle une complexité ?
b.Quel découpage annule le gain ? Donner un exemple.
c.Quelle autre étape peut absorber le bénéfice ?
d.Que faut-il faire pour conclure sur la complexité ?
e.Réécrire son affirmation de façon défendable.
›Voir le corrigéMasquer le corrigé
a. Non. C'est une méthode de conception, pas une garantie de performance.
b. Un découpage déséquilibré, où un sous-problème contient presque tout. Le tri rapide systématiquement mal pivoté dégénère ainsi en O(n²), comme un tri élémentaire.
c. La combinaison : si recoller coûte autant que résoudre directement, le découpage n'apporte rien.
d. Poser la relation de récurrence — coût des sous-problèmes plus coût de combinaison — et la résoudre, par exemple avec l'équation de maître.
e. Par exemple : « Mon algorithme découpe en deux parties de tailles comparables et les recombine en temps linéaire ; la récurrence donne donc O(n log n). » L'affirmation devient vérifiable, alors que la première était une reconnaissance de forme.
4
Tri fusion et tri rapide. Analyser leurs compromis.
Analyser
a.Pourquoi le tri fusion garantit-il O(n log n) dans tous les cas ?
b.Quel coût le tri fusion supporte-t-il que le tri rapide n'a pas ?
c.Quel avantage le tri rapide a-t-il sur l'étape de combinaison ?
d.Pourquoi le choix du pivot est-il tout l'enjeu de son implémentation ?
e.Peut-on désigner un vainqueur ? Justifier.
›Voir le corrigéMasquer le corrigé
a. Parce que les deux moitiés sont égales par construction : la condition de tailles comparables est satisfaite quelles que soient les données. Aucune entrée ne peut le faire dégénérer.
b. De la mémoire supplémentaire pour la fusion : il n'opère pas sur place.
c. Sa combinaison est gratuite : après partition autour du pivot, les deux parties sont déjà à leur place relative, il n'y a rien à recoller.
d. Parce que l'équilibre des tailles en dépend entièrement, et avec lui la complexité — de O(n log n) en moyenne à O(n²) au pire. Toute la qualité de l'implémentation tient à cette stratégie.
e. Non. Le tri fusion offre une garantie au prix de mémoire ; le tri rapide est souvent plus rapide en pratique et sans garantie. Le choix dépend de ce qu'on privilégie : la prévisibilité ou la performance moyenne — et de la mémoire disponible.
Ce qui rapporte des points, ce qui en coûte
Citer les trois étapes et les deux conditions4 ptsPerdu si : Réciter le principe sans ses conditions
Refuser une complexité annoncée par reconnaissance de forme5 ptsPerdu si : Conclure du paradigme à l'efficacité
Expliquer la garantie du tri fusion4 ptsPerdu si : L'attribuer à autre chose qu'aux tailles égales
Relier le pivot à la complexité du tri rapide4 ptsPerdu si : Annoncer O(n log n) sans réserve
Poser une relation de récurrence3 ptsPerdu si : Annoncer une complexité de mémoire
4
La méthode
Concevoir un algorithme diviser pour régner
1
Définir le cas de base, celui qui se résout sans découpage.
2
Choisir le découpage et justifier qu'il produit des sous-problèmes de tailles comparables.
3
Écrire les appels récursifs sur chacun des sous-problèmes.
4
Décrire l'étape de combinaison et évaluer son coût en fonction de la taille traitée.
La fusion de deux moitiés déjà triées se fait en un seul parcours de l'ensemble.
5
Établir la relation de récurrence et en déduire l'ordre de grandeur du coût total.
5
Se tester
Touches 1 à 4
NSITerminale
Question 1
Pour calculer la distance entre la Terre et Mars, la sonde Perseverance utilise un algorithme récursif basé sur le principe diviser pour régner. Voici un extrait de son code. Quelle est la complexité en O(?) de cet algorithme de recherche dichotomique ?
Aucun compte requis — réponds, la correction s'affiche aussitôt.
Paradigme diviser pour régner : c'est en quelle classe ?+
Ce chapitre est au programme de NSI au lycée, en classe de Terminale, année du Baccalauréat. Il est défini par le Bulletin Officiel de l'Éducation nationale, le texte de référence qui fixe ce qui doit être enseigné dans chaque matière.
Que faut-il savoir sur Paradigme diviser pour régner ?+
Principe : décomposer le problème, résoudre les sous-problèmes, combiner. Exemples : tri fusion, tri rapide, recherche dichotomique. Complexité par récurrence : équation de maître. Les notions à maîtriser sont : diviser pour régner, récurrence, tri fusion, tri rapide, complexité, équation de maître.
Où télécharger la fiche PDF de Paradigme diviser pour régner ?+
Sur cette page, dans le bloc « Imprimer » : 3 documents à télécharger — le cours, les exercices et le corrigé — soit 6 pages au format A4, prêtes à imprimer. Le téléchargement est gratuit, immédiat, et ne demande ni compte ni adresse e-mail.
Le corrigé de Paradigme diviser pour régner est-il fourni ?+
Oui, et c'est un document à part : chaque exercice y est repris étape par étape, avec le barème détaillé en fin de fiche — ce qui est attendu, combien de points, et ce qui fait perdre le point. Un parent qui ne se souvient plus du programme peut corriger une copie avec.
Paradigme diviser pour régner peut-il tomber au Baccalauréat ?+
Ce chapitre fait partie du programme officiel de Terminale, il entre donc dans le périmètre du Baccalauréat. Le sujet exact varie chaque année et aucun chapitre n'est garanti, mais l'ensemble du programme de l'année est susceptible d'être évalué : mieux vaut ne pas parier sur des impasses.
Comment réviser Paradigme diviser pour régner efficacement ?+
Commence par lire la fiche de révision pour remettre la règle en place, puis enchaîne immédiatement sur le quiz de cette page. Répondre juste après avoir lu ne suffit pas : reviens sur le chapitre deux ou trois jours plus tard. C'est l'espacement des révisions, plus que leur durée, qui fait tenir une notion en mémoire. Une session de quinze minutes répétée vaut mieux qu'une heure unique.
Faut-il un compte pour s'entraîner sur Paradigme diviser pour régner ?+
Non. Les quiz, les corrections détaillées et les fiches de révision sont accessibles sans créer de compte et sans donner d'adresse e-mail. Le compte gratuit sert uniquement à conserver la progression d'un appareil à l'autre.
Notions voisines
Les chapitres qui traitent des mêmes notions, ici ou dans une autre année.