Diviser pour régner

Introduction

« Diviser pour régner » (divide and conquer) est une stratégie algorithmique générale qui structure beaucoup d'algorithmes efficaces : on découpe un problème en sous-problèmes plus petits du même type, on les résout récursivement, puis on combine les solutions pour construire celle du problème initial. Cette méthode est l'inverse naturelle de la récursion : ce qui descend en récursion se reconstruit en remontant.

La formule latine — divide et impera — date de l'Antiquité : Jules César appliquait à la conquête des Gaules la même logique que l'algorithmicien applique à un tableau de $n$ éléments. Un tournoi de tennis à élimination directe suit le même schéma : à chaque ronde, le nombre de joueurs encore en lice est divisé par deux, jusqu'au vainqueur — un arbre binaire à $\log_2 n$ niveaux.

Le schéma général

Tout algorithme « diviser pour régner » suit trois étapes :

1. Diviser — partitionner l'entrée en sous-entrées plus petites.
2. Régner — résoudre chaque sous-entrée par appel récursif (ou directement si elle est suffisamment petite : c'est le cas de base).
3. Combiner — assembler les sous-solutions en une solution globale.

Le coût d'un tel algorithme s'exprime par une relation de récurrence : si l'on découpe en $a$ sous-problèmes de taille $n/b$, et que les étapes diviser + combiner coûtent $f(n)$, alors

L'intuition par l'arbre des appels

Avant de poser le théorème maître, regardons ce qui se passe à l'exécution. La récurrence $T(n) = 2\,T(n/2) + \mathcal{O}(n)$ du tri fusion engendre un arbre d'appels : à la racine, on traite un tableau de taille $n$ ; au niveau suivant, deux tableaux de taille $n/2$ ; puis quatre de taille $n/4$ ; jusqu'aux feuilles de taille $1$.

• À chaque niveau, le travail total de fusion vaut $\mathcal{O}(n)$ — deux moitiés à $\mathcal{O}(n/2)$, quatre quarts à $\mathcal{O}(n/4)$, etc., somme stable.
• Le nombre de niveaux est $\log_2 n$, puisqu'à chaque descente on divise la taille par $2$.
• Coût total : $\log_2 n$ niveaux $\times\ \mathcal{O}(n)$ par niveau, soit $\mathcal{O}(n \log n)$.

Cette intuition est plus importante à retenir que la table abstraite ci-dessous : elle donne la bonne lecture mentale, le théorème maître en est la version mécanique.

Le théorème maître (forme appliquée)

Le théorème maître donne directement la complexité asymptotique de $T(n) = a \cdot T(n/b) + f(n)$ en comparant $f(n)$ à $n^{\log_b a}$ :

En pratique, seul le cas 2 est à retenir : il couvre le tri fusion et la recherche dichotomique, et c'est celui que vous rencontrerez au baccalauréat. Les cas 1 et 3 relèvent de la culture générale — utiles si vous croisez des récurrences plus exotiques en études supérieures, hors-programme strict ici.

Tri fusion — l'exemple canonique

Le tri fusion (merge sort) est l'exemple type. On divise le tableau en deux moitiés, on trie chacune récursivement, puis on fusionne les deux moitiés triées en une seule.

def fusionner(gauche, droite):
    """Fusionne deux listes déjà triées en une 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

def tri_fusion(tab):
    n = len(tab)
    if n <= 1:                          # cas de base
        return tab
    milieu = n // 2
    g = tri_fusion(tab[:milieu])        # régner sur la gauche
    d = tri_fusion(tab[milieu:])        # régner sur la droite
    return fusionner(g, d)              # combiner

# >>> tri_fusion([5, 2, 8, 1, 4, 7, 3, 6])
# [1, 2, 3, 4, 5, 6, 7, 8]

Analyse de coût : on découpe en $a = 2$ sous-problèmes de taille $n/2$ (donc $b = 2$), la fusion linéaire coûte $f(n) = \mathcal{O}(n)$. On a $n^{\log_b a} = n^{\log_2 2} = n^1 = n$, donc $f(n) = \Theta(n)$ — c'est le cas 2 du théorème maître :

Le tri fusion garantit ce coût en pire cas, ce qui le rend supérieur au tri rapide pour des données potentiellement adverses.

Un mot sur le coût en mémoire

Le tri fusion exposé ci-dessus crée une nouvelle liste à chaque appel — son coût mémoire est en $\mathcal{O}(n)$. Des implémentations en place (qui ne créent pas de copies) existent mais sont plus délicates à écrire. C'est l'un des compromis classiques de l'algorithmique : gagner en mémoire au prix de la simplicité du code.

Autre exemple : rotation d'une image bitmap

Une image bitmap est un tableau 2D de pixels. La rotation d'un quart de tour se résout naïvement en allouant une seconde image et en y recopiant les pixels permutés — coût mémoire $\mathcal{O}(n^2)$ pour une image $n \times n$.

L'approche diviser pour régner divise l'image en quatre quadrants, fait pivoter chaque quadrant récursivement, puis échange les quadrants deux à deux en place. Le coût mémoire devient constant (en ignorant la pile d'appels), au prix d'un code plus subtil.

Recette pour reconnaître un problème « diviser pour régner »

Trois indices :

• Le problème se décompose naturellement en sous-problèmes du même type.
• La résolution d'un cas de base (taille 0 ou 1) est triviale.
• Recombiner les sous-solutions coûte beaucoup moins que le problème entier.

Pour aller plus loin

D'autres algorithmes célèbres reposent sur cette méthode : la transformée de Fourier rapide (FFT, $\mathcal{O}(n \log n)$ pour traiter le signal), l'algorithme de Karatsuba pour la multiplication d'entiers en $\mathcal{O}(n^{1{,}58})$ au lieu de $\mathcal{O}(n^2)$, ou encore la recherche dichotomique (cas particulier où $a = 1$).