Diviser pour régner : un paradigme algorithmique fondamental

Définition

Dans l'approche diviser pour régner, le problème en question est divisé en sous-problèmes plus petits, puis chaque problème est résolu indépendamment. Si nous continuons à diviser les sous-problèmes en sous-problèmes encore plus petits, nous pouvons éventuellement atteindre un stade où plus aucune division n'est possible. Les "sous-problèmes" les plus petits "atomiques" possibles sont résolus. La solution de tous les sous-problèmes est finalement fusionnée afin d'obtenir la solution d'un problème original.

Un algorithme typique de Diviser pour régner résout un problème en utilisant les trois étapes suivantes.

Étape 1 : Diviser

Cette étape implique la décomposition du problème en sous-problèmes plus petits. Les sous-problèmes devraient représenter une partie du problème initial. Cette étape adopte généralement une approche récursive pour diviser le problème jusqu'à ce qu'aucun sous-problème ne soit divisible. À ce stade, les sous-problèmes deviennent de nature atomique mais représentent toujours une partie du problème actuel.

Étape 2 : Régner / Résoudre

Cette étape reçoit beaucoup de problèmes secondaires plus petits à résoudre. Généralement, à ce niveau, les problèmes sont résolus à l'aide de cas de base de l'algorithme récursif.

Étape 3 : Combiner

Lorsque les plus petits problèmes sont résolus, cette étape les combine de manière récursive jusqu'à ce qu'ils formulent une solution au problème initial.

Cette approche algorithmique fonctionne de façon récursive et les étapes de conquête et de fusion fonctionnent si près qu'elles apparaissent comme un seul.

Algorithme générique

Cette approche suit l'algorithme ci-dessous :

Algorithme générique Diviser pour régner Pseudo-code

Fonction DiviserRegner(problème P)
    SI (problème plus petit) ALORS
        Résoudre(P)
    SINON
        Diviser P en P1, P2, P3, ..., Pk
        Appliquer DiviserRegner(P1), DiviserRegner(P2), ..., DiviserRegner(Pk)
        Combiner(DiviserRegner(P1), DiviserRegner(P2), ..., DiviserRegner(Pk))
    FINSI
FINFonction

La condition "problème plus petit" correspond au cas de base de la récursion, où le problème peut être résolu directement sans autre division.

Applications du paradigme Diviser pour régner

Voici quelques algorithmes standard basés sur une approche de programmation diviser pour régner :

La recherche binaire. À chaque étape, l'algorithme compare l'élément d'entrée x à la valeur de l'élément intermédiaire du tableau. Si les valeurs correspondent, retourne l'index du milieu. Sinon, si x est inférieur à l'élément du milieu, l'algorithme est récurrent pour le côté gauche de l'élément du milieu, sinon, pour le côté droit de l'élément du milieu.
Tri rapide (QuickSort). L'algorithme sélectionne un élément de pivot, réorganise les éléments du tableau de manière à ce que tous les éléments plus petits que l'élément de pivot se déplacent vers le côté gauche du pivot et que tous les éléments plus grands se déplacent vers le côté droit. Enfin, l'algorithme trie de manière récursive les sous-tableaux gauche et droit.
Le tri par fusion (MergeSort). L'algorithme divise le tableau en deux moitiés, les trie de façon récursive et fusionne finalement les deux moitiés triées.
Paire de points la plus proche. Le problème est de trouver la paire de points la plus proche dans un ensemble de points dans le plan x-y. Le problème peut être résolu en un temps O(n²) en calculant les distances de chaque paire de points et en comparant les distances pour trouver le minimum. L'algorithme Diviser pour régner résout le problème en temps O(n log n).
L'algorithme de Strassen est un algorithme efficace pour multiplier deux matrices. Une méthode simple pour multiplier deux matrices nécessite 3 boucles imbriquées en temps O(n³). L'algorithme de Strassen multiplie deux matrices en temps O(n^2,807) (approximativement n²·⁸⁰⁷).
L'algorithme Cooley–Tukey de transformation de Fourier rapide (FFT) est l'algorithme le plus courant pour la FFT. C'est un algorithme qui fonctionne en temps O(n log n).
Algorithme de Karatsuba pour la multiplication rapide de grands nombres, qui fonctionne en temps O(n^log₂3) ≈ O(n¹·⁵⁸⁵), plus efficace que la multiplication classique O(n²).

Exemple détaillé : Tri fusion (MergeSort)

Le tri fusion illustre parfaitement le paradigme diviser pour régner :

Étapes du tri fusion

Diviser : Diviser le tableau en deux moitiés (gauche et droite) de taille approximativement égale.
Régner : Trier récursivement chaque moitié en appliquant le même algorithme.
Combiner : Fusionner les deux moitiés triées pour obtenir le tableau complet trié.

def tri_fusion(tab):
    # Cas de base : tableau de taille 0 ou 1 déjà trié
    if len(tab) <= 1:
        return tab
    
    # Diviser
    milieu = len(tab) // 2
    gauche = tab[:milieu]
    droite = tab[milieu:]
    
    # Régner (appels récursifs)
    gauche_trie = tri_fusion(gauche)
    droite_trie = tri_fusion(droite)
    
    # Combiner (fusionner)
    return fusionner(gauche_trie, droite_trie)

def fusionner(gauche, droite):
    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
    
    # Ajouter les éléments restants
    resultat.extend(gauche[i:])
    resultat.extend(droite[j:])
    return resultat

Comparaison des complexités

Algorithme	Complexité (approche naïve)	Complexité (diviser pour régner)
Recherche dans un tableau trié	O(n) (recherche linéaire)	O(log n) (recherche binaire)
Tri	O(n²) (tri à bulles)	O(n log n) (tri fusion, tri rapide)
Paire de points la plus proche	O(n²)	O(n log n)
Multiplication de matrices	O(n³)	O(n²·⁸⁰⁷) (Strassen)
Multiplication de grands nombres	O(n²)	O(n¹·⁵⁸⁵) (Karatsuba)

Points clés à retenir

Le paradigme diviser pour régner consiste à décomposer un problème en sous-problèmes indépendants, les résoudre récursivement, puis combiner leurs solutions.
Les trois étapes fondamentales sont : Diviser (décomposer), Régner (résoudre récursivement), Combiner (fusionner les résultats).
Ce paradigme est particulièrement efficace pour les problèmes qui peuvent être partitionnés naturellement.
De nombreux algorithmes classiques sont basés sur cette approche : recherche binaire, tri fusion, tri rapide, FFT, etc.
La complexité temporelle des algorithmes diviser pour régner est souvent exprimée par des relations de récurrence comme T(n) = a·T(n/b) + f(n).
L'amélioration de complexité par rapport aux approches naïves peut être spectaculaire (exponentielle à logarithmique, quadratique à linéarithmique).

Quand utiliser diviser pour régner ?

Quand le problème peut être divisé en sous-problèmes indépendants de même nature
Quand la combinaison des solutions est plus efficace que de résoudre le problème directement
Pour les problèmes récursifs par nature (arbres, fractales, etc.)
Pour optimiser des algorithmes naïfs (recherche, tri, multiplication)

Sortie

// La sortie apparaîtra ici…

Prêt · Ctrl+Entrée pour exécuter

Suivant la recherche dichotomique

Diviser pour régner : un paradigme algorithmique fondamental