Algorithme diviser pour régner

Diviser pour régner est un paradigme algorithmique très important fondé sur la récursion à branches multiples. Littéralement, cela signifie « diviser pour régner » : un problème complexe est divisé en deux ou plusieurs sous-problèmes identiques ou similaires jusqu'à ce que les sous-problèmes puissent être résolus directement et simplement, et la solution du problème d'origine est la combinaison des solutions des sous-problèmes.

En termes simples, diviser pour régner se compose de trois étapes :Diviser -> Régner -> Combiner。

Imaginez que vous avez devant vous un grand tas de blocs de construction à trier par couleur. Si vous vous y attaquez directement, vous risquez d'être submergé. Une approche plus intelligente consiste à : d'abord diviser le tas en deux plus petits tas, puis trier chaque plus petit tas séparément, et enfin fusionner les deux plus petits tas triés ensemble. CeDiviser pour régnerLe processus est l'idée centrale de l'algorithme diviser pour régner.

Algorithme diviser pour régnerC'est comme la façon dont un chef d'équipe intelligent résout un grand problème :

  1. Diviser: Décomposez le grand problème en plusieurs petits problèmes du même type.
  2. Régner: résoudre récursivement ces sous-problèmes
  3. Combiner: Fusionner les solutions des petits problèmes pour obtenir la solution du problème d'origine.

Cas concrets :

  • Gestion d'entreprise: PDG → Directeur de département → Chef d'équipe → Employé ordinaire
  • Commandement militaire: Commandant → Commandant d'armée → Commandant de division → Commandant de régiment → Commandant de compagnie
  • Organisation des livres: D'abord classer par grande catégorie, puis par sous-catégorie, et enfin trier par ordre alphabétique.
  • Jeu de chasse au trésor: Diviser la grande carte en petits blocs et fouiller chaque bloc
Caractéristiques du problème Autres méthodes Approche diviser pour régner
Données à grande échelle Peut être inefficace Décomposer et traiter en parallèle
Structures complexes Difficile à résoudre directement Simplifier les sous-problèmes
Peut être défini récursivement Nécessite une logique complexe Naturellement adapté à la récursion
Sous-problèmes indépendants Difficile à paralléliser Prend parfaitement en charge le parallélisme

Idées et étapes clés

Les algorithmes de diviser pour régner suivent généralement un cadre clair en trois étapes. Nous pouvons le comprendre intuitivement à l'aide de l'organigramme suivant :

La figure ci-dessus illustre: L'algorithme détermine d'abord si le problème actuel est assez simple pour être résolu directement. Si oui, il le résout directement et renvoie le résultat ; sinon, il décompose le problème en plusieurs sous-problèmes, résout récursivement chaque sous-problème et fusionne enfin les résultats des sous-problèmes pour obtenir la réponse finale.

Plus précisément, ces trois étapes sont :

  1. Diviser: Décomposer le problème d'origine en plusieurs sous-problèmes plus petits, mutuellement indépendants et de même forme que le problème d'origine.
  2. Régner: Résoudre récursivement chaque sous-problème. Si un sous-problème est de taille suffisamment petite, le résoudre directement.
  3. Fusionner: Fusionner les solutions des sous-problèmes pour former la solution au problème d'origine.

Applications classiques des algorithmes diviser pour régner

Pour vous aider à mieux comprendre le fonctionnement de l'algorithme diviser pour régner, examinons deux des exemples les plus classiques.

Application 1 : Tri fusion

Le tri fusion est une parfaite illustration de l'idée de diviser pour régner. Son objectif est detrier un tableau non trié en un tableau trié.。

Étapes de l'algorithme :

  1. Diviser: Diviser le tableau actuel à partir de la position médiane en sous-tableaux gauche et droit.
  2. Régner: Effectuer récursivement un tri fusion sur le sous-tableau gauche et le sous-tableau droit.
  3. Fusion: Fusionner les deux sous-tableaux ordonnés déjà triés en un nouveau tableau ordonné.

Exemple de code :

Exemple

def merge_sort(arr):
    """
Fonction principale du tri fusion
:param arr: La liste à trier
:return: La nouvelle liste triée
    """
    # 1. Conquérir : Si la longueur du tableau est 0 ou 1, retourner directement (cas de base)
    if len(arr) <= 1:
        return arr
   
    # 2. Diviser : Trouver le milieu et diviser le tableau
    mid = len(arr) // 2
    left_half = arr[:mid]   # Sous-tableau gauche
    right_half = arr[mid:]  # Sous-tableau droit
   
    # 3. Conquérir : Trier récursivement les sous-tableaux gauche et droit
    left_sorted = merge_sort(left_half)
    right_sorted = merge_sort(right_half)
   
    # 4. Fusion : Fusionner les deux tableaux triés
    return merge(left_sorted, right_sorted)

def merge(left, right):
    """
Fusionner deux listes triées
:param left: Liste triée A
:param right: Liste triée B
:return: La liste triée fusionnée
    """
    merged = []  # Liste utilisée pour stocker le résultat de la fusion
    i = j = 0    # i et j sont des pointeurs vers left et right, respectivement
   
    # Comparer les têtes des deux listes et mettre le plus petit élément dans merged
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
   
    # Ajouter les éléments restants (s'il y en a) directement à la fin de merged
    # Comme left et right sont déjà triés, la partie restante est également triée
    merged.extend(left[i:])
    merged.extend(right[j:])
   
    return merged

# Données de test
test_array = [38, 27, 43, 3, 9, 82, 10]
print("Tableau d'origine :", test_array)
sorted_array = merge_sort(test_array)
print("Tableau trié :", sorted_array)
# Sortie : Tableau original : [38, 27, 43, 3, 9, 82, 10]
# Sortie : Tableau trié : [3, 9, 10, 27, 38, 43, 82]

Application 2 : Recherche dichotomique

La recherche dichotomique est utilisée dansun tableau triépour localiser rapidement la valeur cible qu'il contient. Elle divise continuellement l'intervalle de recherche en deux, ce qui en fait une version simplifiée de la stratégie diviser pour régner (ne traitant généralement qu'un seul sous-problème, sans besoin de fusionner).

Étapes de l'algorithme :

  1. Diviser: Trouver l'élément du milieu du tableau.
  2. Régner：
    • Si l'élément du milieu est égal à la valeur cible, la recherche réussit.
    • Si la valeur cible est inférieure à l'élément du milieu, rechercher récursivement dans la moitié gauche.
    • Si la valeur cible est supérieure à l'élément du milieu, rechercher récursivement dans la moitié droite.
  3. Fusionner: La recherche dichotomique n'a généralement pas besoin d'étape de fusion, car une fois la valeur cible trouvée, sa position peut être renvoyée directement.

Exemple de code :

Exemple

def binary_search(arr, target, low, high):
    """
Recherche dichotomique (version récursive)
:param arr: Liste triée
:param target: La valeur cible à rechercher
:param low: L'indice de début de la plage de recherche actuelle
:param high: L'indice de fin de la plage de recherche actuelle
:return: L'indice de la valeur cible, ou -1 si elle n'est pas trouvée
    """
    # Cas de base : la plage de recherche est invalide, ce qui signifie que la cible n'est pas trouvée
    if low > high:
        return -1
   
    # Diviser : calculer l'indice du milieu
    mid = (low + high) // 2
   
    # Régner : décider et faire un appel récursif
    if arr[mid] == target:
        return mid  # Cible trouvée, renvoyer l'indice
    elif target < arr[mid]:
        # La cible est dans la moitié gauche, rechercher récursivement dans la moitié gauche
        return binary_search(arr, target, low, mid - 1)
    else:
        # La cible est dans la moitié droite, rechercher récursivement dans la moitié droite
        return binary_search(arr, target, mid + 1, high)

# Données de test (doivent être triées !)
sorted_list = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_value = 23

result = binary_search(sorted_list, target_value, 0, len(sorted_list) - 1)

if result != -1:
    print(f"L'indice de la valeur cible {target_value} dans le tableau est : {result}")
else:
    print(f"La valeur cible {target_value} n'est pas dans le tableau.")
# Sortie : L'indice de la valeur cible 23 dans le tableau est : 5

Caractéristiques et analyse de la complexité des algorithmes de diviser pour régner

Caractéristiques de l'algorithme

Fonctionnalités Description
Le problème peut être décomposé Le problème original doit pouvoir être décomposé en sous-problèmes plus petits et similaires.
Les sous-problèmes sont indépendants Il est préférable que les sous-problèmes soient indépendants les uns des autres, ce qui simplifie leur résolution et leur fusion.
Possède une condition d'arrêt Il doit exister une condition de base simple afin que, lorsque la taille du problème est suffisamment petite, il puisse être résolu directement.
Les solutions peuvent être fusionnées Les solutions des sous-problèmes doivent pouvoir être fusionnées efficacement pour former la solution du problème original.

Analyse de la complexité temporelle

La complexité temporelle des algorithmes diviser pour régner peut généralement être exprimée avecle théorème maîtrepour l'analyser, la forme générale de sa relation de récurrence est : $$ T(n) = aT(\frac{n}{b}) + f(n) $$ où :

  • nest la taille du problème.
  • aest le nombre de sous-problèmes produits par la décomposition.
  • n/best la taille de chaque sous-problème.
  • f(n)est le temps passé sur les étapes de décomposition et de fusion.

Par exemple, pour le tri fusion :

  • a = 2(divisé en deux sous-tableaux)
  • b = 2(la taille de chaque sous-tableau est réduite de moitié)
  • f(n) = O(n)(la fusion de deux tableaux triés prend un temps linéaire)
  • D'après le théorème maître, sa complexité temporelle estO(n log n)。

Exercices pratiques

Maintenant, il est temps de consolider votre compréhension des algorithmes de type diviser pour régner. Veuillez essayer de compléter les exercices suivants :

Exercice 1 : Implémenter le tri rapideLe tri rapide est un autre algorithme classique de type diviser pour régner. Son idée est :

  1. Diviser: Sélectionnez un « pivot » et réorganisez le tableau de sorte que tous les éléments plus petits que le pivot soient placés à gauche et tous les éléments plus grands que le pivot soient placés à droite (opération de partition).
  2. Régner: Effectuez récursivement le tri rapide sur les sous-tableaux à gauche et à droite du pivot.
  3. Fusion: Aucune fusion explicite n'est nécessaire, car après l'opération de partition, le tableau est déjà partiellement ordonné.

Votre tâche: D'après la description ci-dessus, essayez d'écrire du code Python pour le tri rapide.

Exercice 2 : Trouver la somme maximale d'un sous-tableau dans un tableauProblème : Étant donné un tableau d'entiers (pouvant contenir des nombres négatifs), trouvez un sous-tableau contigu dont la somme est maximale. Par exemple, pour[-2, 1, -3, 4, -1, 2, 1, -5, 4], le sous-tableau maximal est[4, -1, 2, 1], et leur somme est6。

Indice (approche diviser pour régner)：

  1. Divisez le tableau en moitiés gauche et droite à partir du milieu.
  2. La somme maximale d'un sous-tableau peut se produire dans :Moitié gauche、Moitié droite, ouÀ cheval sur le point médian。
  3. Résolvez récursivement la somme maximale d'un sous-tableau dans la moitié gauche et la moitié droite.
  4. Calculez la somme maximale d'un sous-tableau qui traverse le point médian (cela nécessite d'accumuler séparément vers la gauche et vers la droite à partir du point médian pour trouver le maximum).
  5. Retournez le maximum des trois.

Essayez de résoudre ce problème en utilisant la stratégie diviser pour régner.

autres extensions