Chapitre 8 - Partie 2 : Diviser pour régner

B.O. spécial n° 8 du 25 juillet 2019 - NSI Terminale

Contenus	Capacités attendues	Commentaires
Méthode « diviser pour régner ».	Écrire un algorithme utilisant la méthode « diviser pour régner ».	La rotation d'une image bitmap d'un quart de tour avec un coût en mémoire constant est un bon exemple. L'exemple du tri fusion permet également d'exploiter la récursivité et d'exhiber un algorithme de coût en n log₂ n dans les pires des cas.

1. Le principe « diviser pour régner »

1.1 Les trois étapes

La méthode diviser pour régner (divide and conquer) résout un problème en trois phases :

Diviser : découper le problème en sous-problèmes plus petits de même nature ;
Régner (résoudre) : résoudre chaque sous-problème récursivement, jusqu'aux cas de base ;
Combiner : assembler les solutions des sous-problèmes pour obtenir la solution du problème initial.

1.2 Lien avec la dichotomie

La recherche dichotomique (vue en première) est un cas particulier : on divise le tableau en deux, on ne résout qu'un seul sous-problème (la moitié contenant la valeur cherchée), et il n'y a pas d'étape de combinaison.

2. Le tri fusion

2.1 Principe

Le tri fusion (merge sort) trie un tableau en appliquant « diviser pour régner » :

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

2.2 Exemple déroulé

Tableau initial : [7, 5, 3, 0, 1, 6, 4, 2]

Diviser :    [7, 5, 3, 0]          [1, 6, 4, 2]
             [7, 5]  [3, 0]        [1, 6]  [4, 2]
             [7] [5] [3] [0]       [1] [6] [4] [2]

Combiner :   [5, 7]  [0, 3]        [1, 6]  [2, 4]
             [0, 3, 5, 7]          [1, 2, 4, 6]
             [0, 1, 2, 3, 4, 5, 6, 7]

2.3 Implémentation

def tri_fusion(tab):
    if len(tab) <= 1:
        return tab

    milieu = len(tab) // 2
    gauche = tri_fusion(tab[:milieu])
    droite = tri_fusion(tab[milieu:])

    return fusionner(gauche, droite)

def fusionner(g, d):
    resultat = []
    i, j = 0, 0
    while i < len(g) and j < len(d):
        if g[i] <= d[j]:
            resultat.append(g[i])
            i += 1
        else:
            resultat.append(d[j])
            j += 1
    resultat.extend(g[i:])
    resultat.extend(d[j:])
    return resultat

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

2.4 Complexité

Le tri fusion a une complexité en O(n log₂ n) dans tous les cas (meilleur, moyen et pire).

Tri	Meilleur cas	Pire cas
Tri sélection (1re)	O(n²)	O(n²)
Tri insertion (1re)	O(n)	O(n²)
Tri fusion	O(n log₂ n)	O(n log₂ n)

Pourquoi O(n log₂ n) ? On divise le tableau en deux à chaque niveau (log₂ n niveaux de récursion) et à chaque niveau, la fusion parcourt tous les n éléments.

2.5 Stabilité

Le tri fusion est stable : deux éléments de même valeur conservent leur ordre relatif initial. C'est grâce au <= dans la comparaison de la fusion.

3. Rotation d'image

3.1 Le problème

On veut faire pivoter une image carrée de 90° dans le sens horaire. L'approche « diviser pour régner » permet de le faire avec un coût en mémoire constant (sans créer de copie de l'image).

3.2 Principe

Diviser : découper l'image en 4 blocs (A, B, C, D) ;
Régner : appliquer récursivement la rotation à chaque bloc ;
Combiner : permuter les 4 blocs pour réaliser la rotation.

 Avant rotation :        Après rotation :
 ┌─────┬─────┐           ┌─────┬─────┐
 │  A  │  B  │           │  D  │  A  │
 ├─────┼─────┤    →      ├─────┼─────┤
 │  D  │  C  │           │  C  │  B  │
 └─────┴─────┘           └─────┴─────┘

3.3 Implémentation simplifiée

def rotation_matrice(matrice):
    n = len(matrice)
    if n <= 1:
        return matrice

    k = n // 2

    # Diviser en 4 blocs
    A = [ligne[:k] for ligne in matrice[:k]]
    B = [ligne[k:] for ligne in matrice[:k]]
    C = [ligne[k:] for ligne in matrice[k:]]
    D = [ligne[:k] for ligne in matrice[k:]]

    # Régner : rotation récursive de chaque bloc
    A = rotation_matrice(A)
    B = rotation_matrice(B)
    C = rotation_matrice(C)
    D = rotation_matrice(D)

    # Combiner : permutation des blocs
    resultat = []
    for i in range(k):
        resultat.append(D[i] + A[i])
    for i in range(k):
        resultat.append(C[i] + B[i])
    return resultat

3.4 Complexité

Temps : O(n²) pour une image n × n (chaque pixel est traité) ;
Mémoire : O(1) dans la version en place (on permute les pixels directement dans l'image sans copie complète).

4. Autres exemples

4.1 Exponentiation rapide

Calculer $x^n$ en réduisant le nombre de multiplications :

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

def puissance_rapide(x, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        demi = puissance_rapide(x, n // 2)
        return demi * demi
    return x * puissance_rapide(x, n - 1)

Complexité : O(log₂ n) au lieu de O(n) pour la méthode naïve.

4.2 Recherche du maximum et du minimum simultanés

Trouver le maximum et le minimum d'un tableau avec moins de comparaisons :

def min_max(tab, debut=0, fin=None):
    if fin is None:
        fin = len(tab) - 1
    if debut == fin:
        return tab[debut], tab[debut]
    if fin == debut + 1:
        if tab[debut] < tab[fin]:
            return tab[debut], tab[fin]
        return tab[fin], tab[debut]

    milieu = (debut + fin) // 2
    min1, max1 = min_max(tab, debut, milieu)
    min2, max2 = min_max(tab, milieu + 1, fin)
    return min(min1, min2), max(max1, max2)

5. Quand utiliser « diviser pour régner » ?

Condition	Description
Décomposable	Le problème peut être découpé en sous-problèmes de même nature
Indépendance	Les sous-problèmes sont indépendants (sinon → programmation dynamique)
Combinaison efficace	La fusion des solutions est rapide

À retenir

Concept	Description
Diviser pour régner	Diviser → Régner (récursion) → Combiner
Tri fusion	Divise en 2, trie récursivement, fusionne. O(n log₂ n)
Fusion	Combiner deux tableaux triés en un seul. O(n)
Rotation d'image	Découper en 4 blocs, tourner chacun, permuter
Exponentiation rapide	O(log₂ n) multiplications au lieu de O(n)
Complexité type	O(n log n) quand on divise en 2 et combine en O(n)