Exemple de diviser pour régner

Si nous devons chercher une définition dans un dictionnaire, nous pouvons parcourir les pages depuis la première jusqu'au moment où nous trouvons la définition. Espérons que l'on ne doive pas trop souvent chercher la définition des zygomatiques.

Intuitivement, lorsque nous cherchons une définition, nous ouvrons le dictionnaire à un endroit où il y a une forte probabilité que les mots définis ne soient pas trop éloignés du mot que nous cherchons, nous comparons les mots de la page ouverte avec celui cherché, et puis nous sautons encore quelques pages en avant ou en arrière jusqu'à trouver la bonne page.

Contents Haut

Principe de diviser pour régner

Nous allons à chaque fois diviser la quantité de données à traiter, jusqu'au moment où nous atteindrons le cas de base. A chaque fois nous devons respecter le fait que la division mène à un cas plus simple : nous dirons qu'il s'agit d'une relation bien fondée.

Nous atteignons le cas de base (minimal) de cette relation bien fondée "<" quand il n'est plus possible de diviser, ce qui peut s'écrire a minimal ⇔ b : b < a

Ensuite, nous devrons combiner tous les éléments.

Nous pouvons employer des boucles pour implémenter ce genre de concept, mais la récursion est vraiment indiquée car nous effectuons la division lors de "la descente" dans la pile des appels récursifs, et nous effectuons la combinaison lors de" la remontée" de la pile.

L'algorithme résoudre(v) de type diviser pour régner peut donc se résumer de la manière suivante :

• v est un cas de base ?
  • si oui : résoudre_directement(v)
  • si non :
    • Phase de décomposition : (v₁, v₂, ..., v_n) := diviser(v) pour lequel v₁, v₂, etc. sont des sous ensembles de v obtenus après division.
    • Phase de récurtion : pour chaque i : r_i = résoudre(v_i) appel à la récursion pour encore diviser notre sous ensemble
    • Phase de recomposition : r = combiner(r₁, r₂, ..., r_n)

Contents Haut

Trier en appliquant diviser pour régner

Nous pouvons appliquer le principe "diviser pour régner" aux différents algorithmes de tri, en remplaçant résoudre(v) par trier(liste_in). Pour nos exemples, nous allons définir certaines conditions:

liste_in : Liste<T>
liste_out : Liste<T>
Post-condition : liste_out est triée², liste_in est une permutation³ de liste_out, et l'ordre de tri est réflexif.

• Le tri par sélection :
  • Info : comme l'algorithme est récursif et retourne à chaque fois une nouvelle liste, liste_i correspond à la liste utilisée au moment i.
  • combiner = cons(v, liste_i) {v est l'élément à mettre en tête si il possède la plus petite valeur des éléments de la liste triée}
  • Cas de base : liste_i = null
  • "diviser" correspond ici à la recherche de la plus petite valeur, en (n)
  • Nous pouvons en déduire que le temps total (diviser + résoudre + combiner) sera de l'ordre de (n²), car il est fait n fois appel à "diviser".
• Le tri par insertion :
  • diviser(liste_i) = {head(liste_i), tail(liste_i)}
  • Cas de base : liste_i = null
  • "combiner" correspond ici à l'insertion d'un élément dans une liste triée, et le temps est proportionnel à la taille de la liste (n)⁴
  • Le temps total sera de l'ordre de (n²)
  • Nous ne constatons donc aucune différence en ordre de grandeur avec le tri par sélection
• Le tri par fusion :
  • Le tri par fusion est par définition un cas typique de diviser pour régner.
  • diviser(liste_i) = liste_i1, liste_i2 tel que liste_i1 + liste_i2 = liste_i et |liste_i1| = |liste_i1| ± 1 en (log n)
  • Cas de base : |liste_i| = 1
  • "combiner" correspond ici à la fusion de deux listes triées en (n)
  • Le temps total sera de l'ordre de (n log n)
  • Le tri par fusion est donc nettement plus efficace en ordre de grandeur que le tri par sélection ou le tri par insertion.