Paradigme Diviser pour Régner
Définition
Le paradigme diviser pour régner (ou divide and conquer) est une approche algorithmique qui consiste à :
- Diviser le problème en sous-problèmes plus petits et similaires.
- Régner en résolvant récursivement chaque sous-problème.
- Combiner les solutions des sous-problèmes pour obtenir la solution finale.
Cette méthode est particulièrement efficace pour résoudre des problèmes dont la structure est récursive.
Exemple emblématique : Tri fusion (Merge Sort)
def tri_fusion(liste):
if len(liste) <= 1:
return liste
# Diviser
milieu = len(liste) // 2
gauche = tri_fusion(liste[:milieu])
droite = tri_fusion(liste[milieu:])
# Régner
return fusion(gauche, droite)
def fusion(gauche, droite):
# Combiner
resultat = []
i = j = 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
Complexité
- Tri fusion : O(n log n) dans tous les cas (meilleur, moyen, pire).
- Recherche dichotomique : O(log n) pour une liste triée.
Cas d'usage
- Tri d'une liste (tri fusion, quicksort).
- Recherche d'un élément (recherche dichotomique).
- Calcul de la puissance (exponentiation rapide).
- Algorithmes géométriques (plus proche paire de points).
Avantages
- Réduction de la complexité grâce à la récursivité.
- Structure modulaire et lisible.
- Adapté aux problèmes de type "diviser pour mieux régner".
Limites
- Peut nécessiter un espace mémoire supplémentaire (ex : stockage des sous-listes).
- Certains problèmes ne se prêtent pas à cette approche.
À retenir : Ce paradigme est une recette universelle pour résoudre des problèmes complexes en les décomposant en étapes simples.