Analyse des algorithmes récursifs

Algorithmique 1 comptait les opérations d'une boucle : deux boucles imbriquées sur $n$ donnent $n^2$, et l'affaire est entendue. Cette méthode s'effondre devant une fonction qui s'appelle elle-même — pour compter ses opérations, il faudrait déjà connaître le coût de l'appel récursif, c'est-à-dire la réponse cherchée.

Ce chapitre donne l'outil qui débloque la situation : on écrit le coût en fonction de lui-même, puis on résout. Il explique enfin d'où sort le $\log n$ du chapitre précédent, et il démontre que ce $n \log n$ n'est pas un hasard mais une limite infranchissable.

Poser l'équation

Le coût d'un algorithme récursif s'écrit comme une équation de récurrence : le coût pour une entrée de taille $n$, exprimé à partir du coût pour des entrées plus petites.

La lecture est mécanique, et il faut prendre l'habitude de la faire ligne à ligne.

1fonction triFusion(T)                   T(n) = ...2    si taille(T) ≤ 1 alors retourner T      cas de base : T(1) = 13    couper T en G et D                      découpe : O(n), parfois O(1)4    G ← triFusion(G)                        un appel sur n/2 : T(n/2)5    D ← triFusion(D)                        un autre : T(n/2)6    retourner fusion(G, D)                  fusion linéaire : O(n)

D'où :

Trois quantités seulement gouvernent ce genre d'équation, et il faut les repérer avant de calculer : combien d'appels récursifs ($a$), sur quelle fraction de l'entrée ($n/b$), et combien coûte le travail non récursif ($f(n)$).

Remarquez la deuxième et la quatrième ligne : le même algorithme, deux équations différentes selon la qualité du pivot. C'est exactement l'écart entre $n \log n$ et $n^2$ du chapitre 3, et il se lit ici avant tout calcul — diviser par deux contre retirer un.

Résoudre par déroulement

La première méthode consiste à remplacer $T$ par sa définition, plusieurs fois, jusqu'à voir le motif.

Le motif apparaît à la troisième ligne : après $k$ déroulements, $T(n) = 2^k\,T(n/2^k) + k\,n$.

Reste à savoir où s'arrêter : quand l'argument atteint le cas de base, c'est-à-dire quand $n/2^k = 1$, donc $k = \log_2 n$. En substituant :

Le $\log_2 n$ est le nombre de fois qu'on peut couper $n$ en deux avant d'arriver à 1. Ce n'est pas une formule à retenir, c'est ce que la division par deux fait.

Résoudre par arbre d'appels

La seconde méthode est plus visuelle, et c'est celle qu'il faut avoir en tête pour raisonner vite. On dessine l'arbre des appels, on calcule le travail effectué à chaque niveau, puis on somme sur les niveaux.

1niveau 0        n                                   travail : n2              ┌─┴─┐3niveau 1     n/2  n/2                               travail : 2 × n/2 = n4            ┌─┴┐  ┌┴─┐5niveau 2   n/4 n/4 n/4 n/4                          travail : 4 × n/4 = n6                  ⋮7niveau k   2^k appels de taille n/2^k               travail : n8                  ⋮9niveau log n    n appels de taille 1                travail : n

Chaque niveau coûte $n$ — c'est le fait remarquable du tri fusion : le nombre d'appels double pendant que leur taille est divisée par deux, donc le produit reste constant. Il y a $\log_2 n$ niveaux. Total : $n \log_2 n$.

Cette lecture rend immédiats les trois régimes possibles, qu'il suffit de reconnaître.

Le travail domine à la racine. Si $f(n)$ décroît plus vite que le nombre d'appels ne croît, la somme est dominée par le premier niveau : $T(n) = \Theta(f(n))$. Exemple : $T(n) = 2T(n/2) + n^2$ donne $\Theta(n^2)$.

Le travail est également réparti. Chaque niveau coûte pareil, et l'on multiplie par le nombre de niveaux : $T(n) = \Theta(f(n) \log n)$. C'est le tri fusion.

Le travail domine aux feuilles. Si le nombre d'appels croît plus vite que $f$ ne décroît, la somme est dominée par le dernier niveau, qui compte $a^{\log_b n} = n^{\log_b a}$ feuilles. Exemple : $T(n) = 2T(n/2) + 1$ donne $\Theta(n)$ — le travail se fait dans les $n$ feuilles.

Ces trois cas constituent, sous une forme informelle, le théorème principal (master theorem). Le comparant à retenir est simple : confronter $f(n)$ à $n^{\log_b a}$.

Une équation ne relève pas de ce schéma et mérite d'être traitée à part : $T(n) = T(n-1) + n$, le pire cas du tri rapide. Ici l'argument ne se divise pas, il décroît de 1 : il y a donc $n$ niveaux, et le travail total vaut $n + (n-1) + \dots + 1 = n(n+1)/2$, soit $\Theta(n^2)$. Le contraste avec $2T(n/2) + n$ tient tout entier dans la façon de réduire l'entrée.

La dichotomie, et pourquoi elle est si rapide

Un seul appel par niveau, et un travail constant : l'arbre d'appels est une ligne de $\log_2 n$ éléments. C'est le premier régime, dégénéré — il n'y a qu'un appel par niveau, donc rien ne s'accumule.

Le chiffre mérite d'être posé, parce qu'il est difficile à croire tant qu'on ne l'a pas écrit : sur un million de valeurs, la recherche séquentielle demande jusqu'à un million de comparaisons, la dichotomie vingt. Sur un milliard, trente.

Pourquoi $n \log n$ est une limite

Reste la question de fond : les deux tris du chapitre 3 s'arrêtent tous deux à $n \log n$. Coïncidence, ou obstacle ?

C'est un obstacle, et il se démontre en trois lignes.

Un tri par comparaison ne peut faire qu'une chose : comparer deux éléments et se brancher selon le résultat. Son exécution se décrit donc par un arbre de décision binaire, dont chaque nœud est une comparaison et chaque feuille une permutation possible du tableau de départ.

Comme l'algorithme doit pouvoir trier n'importe quelle entrée, l'arbre doit posséder au moins $n!$ feuilles — une par permutation. Or un arbre binaire de hauteur $h$ a au plus $2^h$ feuilles. Il faut donc $2^h \ge n!$, c'est-à-dire $h \ge \log_2(n!)$.

La formule de Stirling donne $\log_2(n!) = \Theta(n \log n)$. La hauteur de l'arbre étant le nombre de comparaisons dans le pire cas :

Le tri fusion atteint donc l'optimum de sa catégorie, et aucun algorithme plus astucieux ne descendra sous cette barre.

L'hypothèse « par comparaison » est essentielle, et c'est elle qui laisse une porte ouverte. Un tri qui exploite la structure des clés au lieu de les comparer échappe au raisonnement : le tri par comptage trie $n$ entiers d'un intervalle borné en $O(n)$, en les rangeant directement dans des cases. Il ne contredit pas le théorème, il n'entre pas dans son cadre.

À vous

L'exercice résout les récurrences numériquement, ce qui est le meilleur moyen de vérifier une résolution faite à la main : on programme la récurrence telle qu'elle est écrite, on la tabule, et on compare à la forme close conjecturée.

Trois choses à obtenir. Retrouver $n \log_2 n$ pour le tri fusion et $n(n+1)/2$ pour le pire cas du tri rapide. Compter les niveaux et le travail par niveau d'un arbre d'appels, et voir lequel des trois régimes s'applique. Enfin, comparer $\log_2(n!)$ à $n \log_2 n$ pour constater que la borne inférieure est bien du même ordre que ce que le tri fusion atteint.

// Une récurrence se programme littéralement, avec mémoïsation pour que la
// tabulation reste possible (ch. 2 : ne jamais répondre deux fois).
function resoudre(equation, base) {
  const table = new Map();
  const T = (n) => {
    if (n <= 1) return base;
    if (table.has(n)) return table.get(n);
    const v = equation(n, T);
    table.set(n, v);
    return v;
  };
  return T;
}

// T(n) = 2 T(n/2) + n            — tri fusion
const fusion = resoudre((n, T) => 2 * T(Math.floor(n / 2)) + n, 1);

// T(n) = T(n-1) + n              — tri rapide, pire cas
const rapidePire = resoudre((n, T) => T(n - 1) + n, 1);

// T(n) = T(n/2) + 1              — dichotomie
const dicho = resoudre((n, T) => T(Math.floor(n / 2)) + 1, 1);

// T(n) = 2 T(n/2) + 1            — ← à écrire : quel régime ?
const feuilles = resoudre((n, T) => 0, 1);

function comparer(nom, T, forme, formule) {
  console.log(nom);
  for (const n of [16, 64, 256, 1024, 4096]) {
    const mesure = T(n);
    const conjecture = forme(n);
    const ecart = (mesure / conjecture).toFixed(2);
    console.log("   n = " + String(n).padStart(5) +
      " | T(n) = " + String(mesure).padStart(10) +
      " | " + formule.padEnd(14) + " = " + String(Math.round(conjecture)).padStart(10) +
      " | rapport " + ecart);
  }
}

// ── À VOUS ────────────────────────────────────────────────────────────────
// 1. Écrivez l'équation de « feuilles » et devinez son ordre AVANT de lancer.
// 2. Vérifiez que le rapport T(n) / conjecture tend vers une constante :
//    c'est ce que signifie « du même ordre ».
// 3. Comparez log2(n!) à n·log2(n) : la borne inférieure des tris est-elle
//    bien du même ordre que ce que le tri fusion atteint ?

comparer("T(n) = 2T(n/2) + n   (tri fusion)", fusion, (n) => n * Math.log2(n), "n log2 n");
comparer("T(n) = T(n-1) + n    (rapide, pire cas)", rapidePire, (n) => n * (n + 1) / 2, "n(n+1)/2");

function resoudre(equation, base) {
  const table = new Map();
  const T = (n) => {
    if (n <= 1) return base;
    if (table.has(n)) return table.get(n);
    const v = equation(n, T);
    table.set(n, v);
    return v;
  };
  return T;
}

const fusion = resoudre((n, T) => 2 * T(Math.floor(n / 2)) + n, 1);
const rapidePire = resoudre((n, T) => T(n - 1) + n, 1);
const dicho = resoudre((n, T) => T(Math.floor(n / 2)) + 1, 1);
// Deux appels, travail constant : le nombre d'appels double sans que le
// travail par appel diminue. Le dernier niveau domine, et il compte n
// feuilles : c'est le troisième régime, donc Θ(n).
const feuilles = resoudre((n, T) => 2 * T(Math.floor(n / 2)) + 1, 1);
// Travail quadratique hors récursion : la racine domine, Θ(n²).
const racine = resoudre((n, T) => 2 * T(Math.floor(n / 2)) + n * n, 1);

function comparer(nom, T, forme, formule) {
  console.log(nom);
  for (const n of [16, 64, 256, 1024, 4096]) {
    const mesure = T(n);
    const conjecture = forme(n);
    console.log("   n = " + String(n).padStart(5) +
      " | T(n) = " + String(mesure).padStart(12) +
      " | " + formule.padEnd(14) + " = " + String(Math.round(conjecture)).padStart(12) +
      " | rapport " + (mesure / conjecture).toFixed(2));
  }
  console.log("");
}

comparer("T(n) = 2T(n/2) + n     (tri fusion)", fusion, (n) => n * Math.log2(n), "n log2 n");
comparer("T(n) = T(n-1) + n      (rapide, pire cas)", rapidePire, (n) => n * (n + 1) / 2, "n(n+1)/2");
comparer("T(n) = T(n/2) + 1      (dichotomie)", dicho, (n) => Math.log2(n), "log2 n");
comparer("T(n) = 2T(n/2) + 1     (travail aux feuilles)", feuilles, (n) => n, "n");
comparer("T(n) = 2T(n/2) + n^2   (travail à la racine)", racine, (n) => n * n, "n²");
// Dans les cinq cas le rapport tend vers une constante : c'est exactement ce
// que « du même ordre » veut dire. Le rapport ne tend PAS vers 1 — les
// constantes multiplicatives et les termes d'ordre inférieur subsistent — et
// c'est pourquoi on écrit Θ et non « égale ».

console.log("— la borne inférieure des tris par comparaison —");
// log2(n!) se calcule sans jamais construire n! : log2(a·b) = log2 a + log2 b.
function logFactorielle(n) {
  let s = 0;
  for (let k = 2; k <= n; k++) s += Math.log2(k);
  return s;
}
for (const n of [16, 64, 256, 1024, 4096]) {
  const borne = logFactorielle(n);
  const atteint = n * Math.log2(n);
  console.log("   n = " + String(n).padStart(5) +
    " | log2(n!) = " + String(Math.round(borne)).padStart(7) +
    " | n log2 n = " + String(Math.round(atteint)).padStart(7) +
    " | rapport " + (borne / atteint).toFixed(3));
}
// Le rapport se stabilise autour de 0,9 : log2(n!) et n log2 n sont du même
// ordre, comme l'annonce la formule de Stirling. Autrement dit la borne
// inférieure et ce que le tri fusion atteint ne diffèrent que d'une constante
// — le tri fusion est optimal, et il ne reste aucune marge asymptotique.

En travaux pratiques

dichotomie    T(n) = T(n/2) + O(1)      → O(log n)
tri fusion    T(n) = 2 T(n/2) + O(n)     → O(n log n)
tri rapide    T(n) = 2 T(n/2) + O(n)     → O(n log n)  en moyenne
 pire cas   T(n) = T(n-1)  + O(n)      → O(n²)
Fibonacci     T(n) = T(n-1) + T(n-2)     → O(1,618^n)

théorème général : T(n) = a T(n/b) + f(n)
compare n^(log_b a) à f(n) ; ici a=2, b=2 → n, égal à f(n)
→ O(n log n)

quand n double :          prédit    mesuré
dichotomie   O(log n)      +1 étape   +1 étape      ✓
tri fusion   O(n log n)    ×2,1       ×2,3          ✓
insertion    O(n²)         ×4         ×4,1          ✓
Fibonacci    O(1,618^n)    ×2,6       ×2,6          ✓

/* mais entre n = 2^20 et n = 2^22, le tri fusion fait ×2,9 */

tri fusion, facteur mesuré quand n double :
n < 2^18  (< cache L2) : ×2,1
n = 2^20                : ×2,3
n > 2^22  (> cache L3) : ×2,9

la complexité n'a pas changé ; le COÛT D'UN ACCÈS a changé
(TP 7 d'Architecture : 1 ns en L1, 100 ns en mémoire centrale)

tri fusion, comparaisons mesurées :
n        comparaisons   n log2 n
1 000        8 704        9 966
10 000     120 464      132 877
100 000  1 536 371    1 660 964

rapport comparaisons / (n log2 n) : 0,87, 0,91, 0,92 — STABLE

tri rapide sur 100 000 éléments :
meilleur cas (pivot toujours médian)  : 0,008 s
cas moyen    (entrée aléatoire)       : 0,009 s
pire cas     (entrée triée)           : 24 s

garantie contractuelle → le PIRE cas

en échelle log-log, une complexité en n^k donne une DROITE
de pente k

insertion : pente 2,0    → O(n²)
fusion    : pente 1,05   → O(n log n), presque linéaire
dichotomie: plate         → O(log n)

Ce que la suite en fait

Le bloc III change de sujet mais garde l'outil. Le coût d'une insertion en tête de liste chaînée, d'un empilement, d'un parcours d'arbre : tous s'écrivent en récurrences, et le chapitre 7 posera $T(h) = 2T(h-1) + 1$ pour compter les nœuds d'un arbre binaire complet.

Le $\log n$ reviendra surtout comme promesse conditionnelle. Un arbre binaire de recherche donne des opérations en $O(\log n)$ si sa hauteur reste logarithmique, et en $O(n)$ s'il dégénère en liste — exactement le même écart qu'entre le bon et le mauvais pivot du chapitre 3. Le chapitre 8 montrera ce que coûte de le garantir.

À retenir