Paradigme Diviser pour Régner

Définition

Le paradigme diviser pour régner (ou divide and conquer) est une approche algorithmique qui consiste à :

1. Diviser le problème en sous-problèmes plus petits et similaires.
2. Régner en résolvant récursivement chaque sous-problème.
3. 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.