⚙️ Chapitre : La méthode « diviser pour régner ».
1️⃣ Principe de la méthode
La méthode diviser pour régner consiste à :
- Diviser un problème en sous-problèmes plus petits ;
- Résoudre ces sous-problèmes (souvent récursivement) ;
- Combiner les résultats pour obtenir la solution finale.
Cette méthode est très efficace lorsque les sous-problèmes sont similaires au problème initial. Elle utilise souvent la récursivité.
Structure générale :
def diviser_regner(probleme):
if cas_simple(probleme):
return solution_simple
sous_problemes = diviser(probleme)
solutions = [diviser_regner(p) for p in sous_problemes]
return combiner(solutions)
2️⃣ Exemple simple : la recherche dichotomique
La recherche dichotomique permet de chercher une valeur dans une liste triée.
- On regarde l'élément du milieu ;
- Si c'est la valeur cherchée → terminé ;
- Sinon on recommence dans la moitié gauche ou droite.
Liste : [2, 5, 8, 12, 16, 23, 38] — On cherche 16.
On coupe en deux → on compare avec 12.
16 est plus grand → on garde la moitié droite. On recommence jusqu'à trouver 16.
def recherche_dichotomique(tab, valeur):
gauche, droite = 0, len(tab) - 1
while gauche <= droite:
milieu = (gauche + droite) // 2
if tab[milieu] == valeur:
return milieu
elif tab[milieu] < valeur:
gauche = milieu + 1
else:
droite = milieu - 1
return -1
Dans le pire des cas, on divise la taille par 2 à chaque étape. Le nombre d'étapes est donc proportionnel à \(\log_2(n)\).
Exemple : la recherche dichotomique d'un mot dans un dictionnaire
Dans cette animation sur le site PhysAlgo,
on ouvre un dictionnaire de 386264 mots au milieu, puis on élimine la moitié inutile.
Avec cette méthode, on trouve le mot en 19 essais dans le pire des cas.
En effet, \(\log_2(386264) \approx 18{,}6\).
3️⃣ Le tri fusion : diviser pour régner appliqué au tri
Le tri fusion est un algorithme de tri basé sur la même idée :
- Diviser la liste en deux ;
- Trier chaque moitié ;
- Fusionner les deux listes triées.
[8, 3, 6, 2] → on divise : [8, 3] et [6, 2] → on divise encore : [8], [3], [6], [2]
→ on fusionne : [3, 8] et [2, 6] → fusion finale : [2, 3, 6, 8]
4️⃣ Implémentation simple du tri fusion
def fusion(gauche, droite):
resultat = []
i, j = 0, 0
while i < len(gauche) and j < len(droite):
if gauche[i] < droite[j]:
resultat.append(gauche[i]); i += 1
else:
resultat.append(droite[j]); j += 1
resultat.extend(gauche[i:])
resultat.extend(droite[j:])
return resultat
def tri_fusion(tab):
if len(tab) <= 1:
return tab
milieu = len(tab) // 2
gauche = tri_fusion(tab[:milieu])
droite = tri_fusion(tab[milieu:])
return fusion(gauche, droite)
5️⃣ Complexité du tri fusion
- On divise la liste en deux à chaque niveau ;
- On effectue une fusion proportionnelle à
n; - Le nombre de niveaux est \(\log_2(n)\).
\[O(n \times \log_2(n))\]
6️⃣ Animation : ordre réel des appels récursifs
L'animation ci-dessous montre l'exécution dans l'ordre DFS réel de l'algorithme récursif, avec la pile d'appels et le pseudocode synchronisés à chaque étape.
🔹 Ce qu'il faut comprendre
- On descend en divisant — la pile grossit.
- On remonte en fusionnant — la pile se vide.
- La branche gauche est entièrement traitée avant la branche droite.
- Il y a environ \(\log_2(n)\) niveaux, chacun coûte \(n\) opérations.
C'est cette structure en arbre qui explique la complexité en \(O(n \times \log_2(n))\).
7️⃣ À retenir
- Diviser pour régner consiste à découper un problème en sous-problèmes.
- La recherche dichotomique est un premier exemple simple.
- Le tri fusion applique cette méthode au tri.
- Sa complexité est en \(n \times \log_2(n)\), bien meilleure que \(n^2\).
La méthode « diviser pour régner » est fondamentale en algorithmique et permet de concevoir des algorithmes très performants.
🔗 Aucun exercice sur le tri fusion dans la base.