NSI · Terminale · Algorithmique
Diviser pour régner
Couper, résoudre, recoller.
En bref
Diviser pour régner est une stratégie en trois temps : diviser le problème en sous-problèmes de même nature, les résoudre récursivement, combiner leurs solutions.
Les trois étapes
| Étape | Ce qu’elle fait |
|---|---|
| Diviser | Découper l’entrée en parties, généralement deux moitiés |
| Régner | Résoudre chaque partie par un appel récursif, jusqu’au cas de base |
| Combiner | Reconstruire la solution globale |
C’est la troisième étape qui distingue les algorithmes : triviale pour la recherche dichotomique, coûteuse pour le tri fusion.
La recherche dichotomique
Sur un tableau trié, on compare la valeur cherchée à l’élément du milieu : chaque comparaison écarte la moitié du tableau.
| Méthode | Comparaisons pour un million d’éléments |
|---|---|
| Recherche séquentielle | jusqu’à 1 000 000 |
| Recherche dichotomique | environ 20 |
La condition est absolue : le tableau doit être trié. Sur un tableau non trié, la dichotomie ne signale rien — elle renvoie simplement un résultat faux.
Le tri fusion
| Étape | Ce qu’elle fait |
|---|---|
| Diviser | Couper le tableau en deux moitiés |
| Régner | Trier chaque moitié récursivement |
| Combiner | Fusionner les deux moitiés triées en prenant à chaque étape le plus petit élément disponible |
| Sa qualité | Son défaut |
|---|---|
| n log n dans tous les cas — la borne optimale des tris par comparaison | Un tableau auxiliaire : mémoire proportionnelle à n |
| Stable : deux éléments égaux gardent leur ordre | — |
| Performance indépendante des données | — |
L’ordre de grandeur qui décide
| Tri | Coût | Pour un million d’éléments |
|---|---|---|
| Insertion, sélection | n² | environ 10¹² opérations |
| Fusion | n log n | environ 2 × 10⁷ opérations |
Ce n’est pas une nuance, mais la différence entre « instantané » et « impossible ».
Les autres exemples
Exponentiation rapide (élever au carré plutôt que multiplier n fois), tri rapide, multiplication de Karatsuba, enveloppe convexe, transformée de Fourier rapide.
Quand la stratégie ne s’applique pas
Il faut que les sous-problèmes soient indépendants. Quand ils se recouvrent, diviser pour régner recalcule inutilement — et c’est la programmation dynamique qui prend le relais.
Retenir la mécanique du logarithme : diviser la taille par deux à chaque étape, c’est atteindre 1 en log₂(n) étapes. Tout le chapitre en découle.
Teste-toi
6 questions pour vérifier
Touche une réponse : la correction s’affiche tout de suite.
1.Quelles sont les trois étapes de la stratégie « diviser pour régner » ?
2.Quelle condition la recherche dichotomique exige-t-elle ?
3.Quel est le coût d’une recherche dichotomique sur n éléments ?
4.Quel est le coût du tri fusion ?
5.Quel est le principal inconvénient du tri fusion ?
6.Un tri est dit stable quand deux éléments égaux gardent leur ordre d’origine.
0 / 6 questions
Dans l’app, ce chapitre a son quiz complet, chronométré, et tes erreurs reviennent au bon moment pour ne plus les refaire.
La fiche de révision, sur une page
Tout « Diviser pour régner » sur une seule page A4 illustrée : l’essentiel, les pièges et un mini-test. Elle se débloque dans l’app avec des gemmes — et ton compte gratuit en offre assez pour tes trois premières fiches.
