Méthode « diviser pour régner »

Une technique souvent efficace, lorsqu'elle est possible, consiste à diviser un problème en plusieurs sous-problèmes indépendants, puis à les résoudre récursivement.

IPrincipe

Le paradigme de programmation « diviser pour régner » (ou divide and conquer) consiste à ramener la résolution d'un problème dépendant d'un entier $n$ à la résolution de un ou plusieurs sous-problèmes indépendants dont la taille des entrées passe de $n$ à $\frac{n}{2}$ ou une fraction de $n$.

Les algorithmes ainsi conçus s'écrivent de manière naturelle de façon récursive. Le procédé « diviser pour régner » est un cas particulier de la récursivité, où la taille du problème est divisée à chaque appel récursif plutôt que seulement réduite d'une unité.

IIExemple de l'exponentiation rapide

Le calcul de la puissance d'un nombre définie par $a^0=1$ et $a^n=a\times a^{n-1}$ n'est pas optimal. Il peut être amélioré de la manière suivante :

$a^0=1$ ;

si $n$ est pair, $a^n={\left(a\times a\right)}^{n/2}$ ;

sinon $a^n=a\times {\left(a\times a\right)}^{\left(n-1\right)/2}$.

La taille du problème est divisée par deux à chaque appel récursif. On a donc une relation de récurrence de la forme $T\left(n+1\right)\le T\left(\frac{n}{2}\right)$ et $T\left(1\right)=1$ qui mène à $T\left(n\right)=\text{Θ}\left({\log }_2\left(n\right)\right)$.

IIITri fusion

Le tri fusion permet de trier une liste lst selon le principe « diviser pour régner ».

Pour rassembler deux listes lst1 et lst2 déjà triées, on peut les interclasser de manière suivante : on compare les plus petits éléments de chacune d'elles, on place le plus petit des deux dans une nouvelle liste lstn et on poursuit cette opération jusqu'à épuisement de l'une des deux listes. On complète alors lstn en ajoutant à la fin de celle-ci les éléments de la liste non vide.

Le tri fusion est alors défini de la manière suivante :

si la liste lst a au plus un élément elle est déjà triée ;

si la liste lst a deux éléments ou plus, on partage lst en deux sous-listes de même taille, à un élément près, puis on appelle récursivement la fonction sur chacune des sous-listes et on interclasse les sous-listes triées.

Exemple illustré par un schéma :

Exemple de programme en Python :

IVComplexités typiques