Diviser pour régner

Le paradigme diviser pour régner

Le paradigme diviser pour régner (divide and conquer) est une méthode de conception d’algorithmes qui repose sur trois étapes :

1. Diviser : découper le problème initial en sous-problèmes plus petits de même nature ;
2. Régner : résoudre chaque sous-problème récursivement, jusqu’à obtenir des cas suffisamment simples pour être résolus directement ;
3. Combiner : assembler les solutions des sous-problèmes pour construire la solution du problème initial.

Ce paradigme est particulièrement efficace lorsque le découpage réduit significativement la taille des données à traiter à chaque étape. La plupart des algorithmes DPR divisent le problème en deux moitiés, ce qui conduit à des complexités en $O(n \log n)$ au lieu de $O(n^2)$.

Recherche dichotomique

Principe

La recherche dichotomique (binary search) recherche un élément dans un tableau trié en divisant l’espace de recherche par deux à chaque étape.

Au lieu de parcourir tous les éléments un par un ($O(n)$), on compare l’élément cherché au milieu du tableau :

• s’il est égal, on a trouvé ;
• s’il est inférieur, on cherche dans la moitié gauche ;
• s’il est supérieur, on cherche dans la moitié droite.

Version itérative

def recherche_dichotomique(x, tab):
    """Renvoie l'indice de x dans tab (trié), ou -1 si absent."""
    gauche = 0
    droite = len(tab) - 1
    while gauche <= droite:
        milieu = (gauche + droite) // 2
        if tab[milieu] == x:
            return milieu
        elif tab[milieu] < x:
            gauche = milieu + 1
        else:
            droite = milieu - 1
    return -1

Version récursive

def recherche_dicho_rec(x, tab, gauche, droite):
    """Version récursive de la recherche dichotomique."""
    if gauche > droite:
        return -1
    milieu = (gauche + droite) // 2
    if tab[milieu] == x:
        return milieu
    elif tab[milieu] < x:
        return recherche_dicho_rec(x, tab, milieu + 1, droite)
    else:
        return recherche_dicho_rec(x, tab, gauche, milieu - 1)

Complexité

À chaque étape, l’intervalle de recherche est divisé par deux. Si le tableau contient $n$ éléments, le nombre maximal d’étapes est le nombre de fois qu’on peut diviser $n$ par deux, soit $\lfloor \log_2 n \rfloor + 1$.

La complexité de la recherche dichotomique est donc en $O(\log n)$, bien meilleure que la recherche séquentielle en $O(n)$.

Tri fusion

Principe

Le tri fusion (merge sort) est un algorithme de tri qui applique le paradigme diviser pour régner :

1. Diviser : couper le tableau en deux moitiés ;
2. Régner : trier récursivement chaque moitié ;
3. Combiner : fusionner les deux moitiés triées en un seul tableau trié.

Le cas de base est un tableau de zéro ou un élément, déjà trié par définition.

La fonction de fusion

L’étape clé est la fusion de deux tableaux triés. On parcourt les deux tableaux simultanément en prenant à chaque fois le plus petit élément.

def fusion(gauche, droite):
    """Fusionne deux listes triées en une seule liste triée."""
    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

Le tri fusion complet

def tri_fusion(tab):
    """Trie une liste par l'algorithme du tri fusion."""
    if len(tab) <= 1:
        return tab
    milieu = len(tab) // 2
    gauche = tri_fusion(tab[:milieu])
    droite = tri_fusion(tab[milieu:])
    return fusion(gauche, droite)

Exemple pas à pas

Tri fusion de [38, 27, 43, 3, 9, 82, 10] :

[38, 27, 43, 3, 9, 82, 10]
       /                \
[38, 27, 43]        [3, 9, 82, 10]
   /      \            /        \
[38]   [27, 43]    [3, 9]    [82, 10]
        /    \      /   \      /    \
      [27]  [43]  [3]  [9]  [82]  [10]
        \    /      \   /      \    /
      [27, 43]    [3, 9]    [10, 82]
   \      /            \        /
[27, 38, 43]        [3, 9, 10, 82]
       \                /
[3, 9, 10, 27, 38, 43, 82]

Complexité

À chaque niveau de récursion, on divise le tableau en deux moitiés. Il y a donc $\log_2 n$ niveaux. À chaque niveau, la fusion parcourt l’ensemble des $n$ éléments.

La complexité du tri fusion est en $O(n \log n)$, dans tous les cas (meilleur, pire et moyen). C’est une amélioration majeure par rapport aux tris par sélection et par insertion qui sont en $O(n^2)$.

Inconvénient : le tri fusion nécessite de la mémoire supplémentaire pour stocker les sous-tableaux lors de la fusion (il n’est pas en place).

Exponentiation rapide

L’exponentiation rapide calcule $a^n$ en exploitant la parité de l’exposant :

$$a^n = \begin{cases} 1 & \text{si } n = 0 \ (a^{n/2})^2 & \text{si } n \text{ est pair} \ a \times (a^{(n-1)/2})^2 & \text{si } n \text{ est impair} \end{cases}$$

def puissance(a, n):
    """Calcule a^n par exponentiation rapide."""
    if n == 0:
        return 1
    if n % 2 == 0:
        demi = puissance(a, n // 2)
        return demi * demi
    else:
        demi = puissance(a, (n - 1) // 2)
        return a * demi * demi

Au lieu de $n - 1$ multiplications (méthode naïve), l’exponentiation rapide n’en effectue que $O(\log n)$.

Synthèse : reconnaître un algorithme DPR

Pour qu’un algorithme relève du paradigme diviser pour régner, il faut identifier :

1. le découpage du problème en sous-problèmes de même nature ;
2. le cas de base qui arrête la récursion ;
3. l’étape de combinaison des résultats.