Diviser pour régner

Contenus

La méthode de diviser pour régner est une méthode qui permet, parfois de trouver des solutions efficaces à des problèmes algorithmiques. L’idée est de découper le problème initial, de taille n, en plusieurs sous-problèmes de taille inférieure, puis de recombiner les solutions partielles jusqu’à obtenir la solution finale.

Principe

Contrairement à la programmation dynamique, les résultats des sous-problèmes ne sont utiles que pour le résultat du problème parent.

L’algorithme de diviser pour régner se décompose en trois étapes :

Diviser : le problème est découpé en sous-problèmes de taille n/b. Ces sous-problèmes sont de même nature que leur parent. Nous sommes donc en présence de a sous-problèmes identiques. Lorsque b=2, nous parlons de dichotomie.
Régner : les sous-problèmes sont résolus récursivement.
Recombiner : les solutions des sous-problèmes sont recombinés pour reconstruire la solution au problème initial.

Exemple

Afin de mieux comprendre la construction de l’algorithme, nous prendrons exemple sur l’exponentiation rapide. Le principe de cet algorithme est de calculer xⁿ.

Une méthode naïve consisterait à faire une boucle où a*= x avec a = 1 initialement. La complexité de la méthode naïve est donc linéaire 0(n).

Afin d’utiliser la méthode diviser pour régner, nous devons trouver un programme mathématique permettant de réécrire notre problème en sous-problèmes équivalant. Puisqu’il s’agit d’une méthode récursive, il ne faut pas oublier d’inclure un état final. Nous sommes donc en présence du programme mathématique suivant :

Diviser pour régner exponentiation rapide

L’algorithme est le suivant :

double puissance(double x, int n)
{
   if (n==0) return 1;
   else {
      if (n%2==0) return puissance (x*x, n/2);
      else return x*puissance(x*x, (n-1)/2);
      end if
   end if
}

Sa complexité est en 0(log n) – taille de l’arbre binaire complet à n sommets.