Méthode “Diviser pour régner”
1. Le principe
La méthode “diviser pour régner” (divide and conquer en anglais) consiste à diviser un problème complexe en plusieurs sous-problèmes plus simples, puis à résoudre ces sous-problèmes séparément avant de les combiner pour obtenir la solution finale du problème initial. Cette méthode permet souvent de simplifier les calculs et de trouver des solutions plus rapidement que si on essayait de résoudre le problème dans son ensemble. Elle est utilisée dans de nombreux domaines, tels que l’informatique, les mathématiques et les sciences de l’ingénieur.
Cette méthode peut par exemple permettre de paralléliser le traitement des sous-problèmes, ce qui peut accélérer encore davantage la recherche de solutions.
Les inconvénients : la nécessité de décomposer un problème complexe en sous-problèmes, ce qui peut prendre du temps et nécessiter une certaine expertise. De plus, il peut être difficile de combiner les solutions des sous-problèmes pour obtenir une solution finale pour le problème initial. En conséquence, la méthode “diviser pour régner” peut ne pas être adaptée à tous les types de problèmes et peut ne pas être la plus efficace dans certains cas.
2. Exemple
Nous avons déjà rencontré cette méthode : recherche dichotomique dans une ABR et tous les algorithmes de type “dichotomie” (rencontrés en mathématiques par exemple).
L’algorithme de tri fusion (merge sort en anglais) est un algorithme de tri utilisé pour trier des éléments dans un ordre croissant ou décroissant. Il fonctionne en divisant récursivement la liste d’éléments à trier en sous-listes plus petites jusqu’à ce qu’il ne reste plus qu’une seule valeur dans chaque sous-liste. Ces sous-listes sont ensuite fusionnées en une seule liste triée en comparant les valeurs de chaque sous-liste et en plaçant les valeurs plus petites en premier.
Il s’agit d’une utilisation classique de la méthode “diviser pour régner” : à chaque étape, on appelle récursivement la même fonction, mais avec une liste dont la taille a été divisée par deux.
Voici une description de cet algorithme en pseudo-code :
fonction tri_fusion(liste : tableau d'entiers) -> tableau d'entiers
si longueur(liste) <= 1
retourner liste
sinon
milieu = longueur(liste) / 2
liste_gauche = tri_fusion(liste[1...milieu])
liste_droite = tri_fusion(liste[milieu+1...longueur(liste)])
retourner fusionner(liste_gauche, liste_droite)
fonction fusionner(liste_gauche : tableau d'entiers, liste_droite : tableau d'entiers) -> tableau d'entiers
// Initialiser les indices des sous-listes et de la liste originale
i = 0
j = 0
liste_fus = []
// Fusionner les deux sous-listes en comparant les éléments de chaque liste
tant que i < longueur(liste_droite) et j < longueur(liste_gauche)
si liste_droite[i] <= liste_gauche[j]
ajouter liste_droite[i] à liste_fus
i = i + 1
sinon
ajouter liste_gauche[j] à liste_fus
j = j + 1
// Copier les éléments restants de la liste_droite (s'il y en a)
tant que i < longueur(liste_droite)
ajouter liste_droite[i] à liste_fus
i = i + 1
// Copier les éléments restants de la liste_gauche (s'il y en a)
tant que j < longueur(liste_gauche)
ajouter liste_gauche[j] à liste_fus
j = j + 1
// Retourner la liste fusionnée
retourner liste_fusDérouler à la main l’exécution de cet algorithme avec la liste [5, 2, 4, 6, 1, 3]. Présenter ce déroulement sous forme d’un arbre.
Pour utiliser cet algorithme, on peut appeler la fonction tri_fusion en lui passant la liste d’entiers à trier.
Implémentation en Python :
def tri_fusion(liste):
if len(liste) <= 1:
return liste
else:
milieu = len(liste) // 2
liste_gauche = tri_fusion(liste[:milieu])
liste_droite = tri_fusion(liste[milieu:])
return fusionner(liste_gauche, liste_droite)
def fusionner(liste_gauche, liste_droite):
# Initialiser les indices des sous-listes et de la liste originale
i = 0
j = 0
liste_fus = []
# Fusionner les deux sous-listes en comparant les éléments de chaque liste
while i < len(liste_droite) and j < len(liste_gauche):
if liste_droite[i] <= liste_gauche[j]:
liste_fus.append(liste_droite[i])
i = i + 1
else:
liste_fus.append(liste_gauche[j])
j = j + 1
# Copier les éléments restants de la liste_droite (s'il y en a)
while i < len(liste_droite):
liste_fus.append(liste_droite[i])
i = i + 1
# Copier les éléments restants de la liste_gauche (s'il y en a)
while j < len(liste_gauche):
liste_fus.append(liste_gauche[j])
j = j + 1
# Retourner la liste fusionnée
return liste_fusTest du programme en console :
>>> liste = [5, 2, 4, 6, 1, 3]
>>> tri_fusion(liste)
>>> print(liste)
[1, 2, 3, 4, 5, 6]Visualisation de l’exécution avec Python Tutor :
Complexité de l’algorithme
L’aspect “dichotomique” de l’algorithme correspond à une complexité en \(\log_2 n\), où \(n\) est la taille de la liste à trier. Cependant, la fonction de fusion de deux listes triées est, elle en \(\mathcal{O}(n)\).
Au final, on a donc le résultat suivant :
La complexité (temporelle) de l’algorithme de tri fusion est en \(\mathcal{O}(n\log n)\), où \(n\) est la taille de la liste à trier.
Il s’agit donc d’une complexité quasi-linéaire.
Comme nous l’avons vu dans les rappels d’algorithmique, une telle complexité est bien meilleure qu’une complexité quadratique et moins bonne qu’une complexité linéaire, comme illustré ci-dessous.
Pour rappel, les algorithmes de tri étudiés en première (tri par insertion et tri pas sélection) sont de coût quadratique dans le pire des cas.