Diviser pour régner

13.1 Le principe

La programmation dynamique résout un problème à partir de tous ses sous-problèmes, qui se recouvrent et sont mémorisés dans un tableau. La méthode diviser pour régner découpe au contraire le problème en quelques sous-problèmes indépendants, de tailles nettement plus petites (souvent la moitié), les résout récursivement, et combine leurs solutions.

13.2 Premiers exemples sur les intervalles

13.2.1 Afficher un intervalle

Écrivons une fonction récursive qui affiche les valeurs de l'intervalle $[i:j]$ dans l'ordre croissant. On coupe l'intervalle en son milieu $k=\lfloor (i+j)/2\rfloor$ : $[i:j]=[i:k]\cup \{k\}\cup [k+1:j]$, et toutes les valeurs de $[i:k]$ sont inférieures à $k$, elles-mêmes inférieures à celles de $[k+1:j]$.

static void arc(int i, int j) { // affiche [i:j] dans l'ordre croissant
    if (j - i <= 0) return;      // [i:j] vide : rien à afficher
    int k = (i + j) / 2;         // i <= k < j
    arc(i, k);                   // [i:k] affiché croissant
    System.out.print(k + " ");   // puis k
    arc(k + 1, j);               // puis [k+1:j] : [i:j] affiché croissant
}

static void ard(int i, int j) { // affiche [i:j] dans l'ordre décroissant
    if (j - i <= 0) return;
    int k = (i + j) / 2;
    ard(k + 1, j);               // [k+1:j] affiché décroissant
    System.out.print(k + " ");   // puis k
    ard(i, k);                   // puis [i:k]
}

arc(0,8) : 0 1 2 3 4 5 6 7
ard(0,8) : 7 6 5 4 3 2 1 0

Les deux appels récursifs portent sur des intervalles strictement plus petits que $[i:j]$ (car $i\le k<j$) : la récursivité se termine. Pour l'ordre décroissant, il suffit d'inverser l'ordre des deux appels. C'est exactement le schéma des parcours grd et drg d'un arbre binaire de recherche (chapitre 9).

13.2.2 Somme par moitiés

static int somme(int[] T, int i, int j) { // retourne la somme de T[i:j]
    if (j - i == 0) return 0;
    if (j - i == 1) return T[i];
    int k = (i + j) / 2;
    return somme(T, i, k) + somme(T, k, j);
}

Ce découpage n'apporte rien par rapport à une boucle (les deux sont en $\Theta (n)$), mais il a deux vertus : il se parallélise naturellement (les deux moitiés peuvent être calculées par deux processeurs), et, en calcul flottant, il accumule moins d'erreurs d'arrondi qu'une somme séquentielle.

13.2.3 Arbre binaire de recherche de hauteur minimum

Au chapitre 9 nous avons construit un arbre binaire de recherche de hauteur minimum sur les valeurs $[i:j]$ : la racine est la médiane $k$, les sous-arbres gauche et droit sont des arbres de hauteur minimum sur $[i:k]$ et $[k+1:j]$. C'est un « diviser pour régner » en cinq lignes :

static AB abrhm(int i, int j) {
    if (j - i <= 0) return null;             // [i:j] vide : arbre vide
    int k = (i + j) / 2;                     // valeur médiane de [i:j]
    return new AB(k, abrhm(i, k), abrhm(k + 1, j));
}

13.3 Temps de calcul d'un algorithme récursif

Notons $T(n)$ le temps de calcul dans le pire cas sur un problème de taille $n$. Pour un algorithme qui découpe en $a$ sous-problèmes de taille $n/b$ et dont la division et la combinaison coûtent $f(n)$ :

$$T(n)=aT(n/b)+f(n),T(1)=\text{constante}.$$

13.3.1 L'arbre des appels

Prenons $T(n)=2T(n/2)+\alpha n$ (deux moitiés, combinaison linéaire : c'est le cas du tri par fusion, chapitre 14). Dessinons l'arbre des appels, en notant dans chaque nœud le coût de la combinaison :

Au niveau $p$ il y a $2^p$ appels, chacun sur un problème de taille $n/2^p$ : le coût total du niveau est $2^p\times \alpha n/2^p=\alpha n$. La taille est divisée par $2$ à chaque niveau, il y a donc ${\log }_{2}n$ niveaux, et

$$T(n)=\alpha n{\log }_{2}n+\beta n\Rightarrow T(n)=\Theta (n\log n).$$

Avec le même raisonnement :

• $T(n)=T(n/2)+\alpha$ (dichotomie, chapitre 12) : ${\log }_{2}n$ niveaux de coût $\alpha$, donc $\Theta (\log n)$ ;
• $T(n)=2T(n/2)+\alpha$ (somme par moitiés) : les niveaux coûtent $\alpha ,2\alpha ,4\alpha ,\dots ,n\alpha$, au total moins de $2n\alpha$, donc $\Theta (n)$ ;
• $T(n)=4T(n/2)+\alpha n$ : le niveau $p$ coûte $2^p\alpha n$ ; le dernier niveau domine avec $4^{{\log }_{2}n}=n^2$ feuilles : $\Theta (n^2)$.