Trois Fibonacci, trois complexités


/* (a) recursion naive : Theta(phi^n) appels, Theta(n) d'espace de pile */
long fib_naif(int n) {
    if (n < 2) { return n; }
    return fib_naif(n - 1) + fib_naif(n - 2);
}

/* (b) iteration : Theta(n) additions, Theta(1) d'espace */
long fib_iter(int n) {
    long a = 0, b = 1;
    /* INVARIANT : a == F(i) et b == F(i+1), ou i est le nombre de tours faits. */
    for (int i = 0; i < n; i = i + 1) { long c = a + b; a = b; b = c; }
    return a;
}

/* (c) memoisation : Theta(n) appels, Theta(n) d'espace (le tableau) */
long fib_memo(int n, long memo[]) {
    if (n < 2) { return n; }
    if (memo[n] >= 0) { return memo[n]; }
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo);
    return memo[n];
}

Le comptage des appels, mesuré :


  n | F(n)     | appels naifs | 2*F(n+1)-1 | appels memoises | 2n-1
  5 |        5 |           15 |         15 |               9 |    9
 10 |       55 |          177 |        177 |              19 |   19
 20 |     6765 |        21891 |      21891 |              39 |   39
 30 |   832040 |      2692537 |    2692537 |              59 |   59
 35 |  9227465 |     29860703 |   29860703 |              69 |   69

La formule exacte du nombre d'appels naïfs est $2 F_{n + 1} - 1$ , et la mesure la confirme sur les cinq lignes. On la démontre par récurrence : notons $A_{n}$ le nombre d'appels. $A_{0} = A_{1} = 1 = 2 F_{1} - 1 = 2 F_{2} - 1$ , et $A_{n} = 1 + A_{n - 1} + A_{n - 2}$ donne $A_{n} = 1 + 2 F_{n} - 1 + 2 F_{n - 1} - 1 = 2 F_{n + 1} - 1$ . Comme $F_{n} \sim φ^{n} / 5$ avec $φ = (1 + 5) /2$ , la récursion naïve est en $Θ (φ^{n})$ : exponentielle.

Le tableau récapitulatif :

	Temps	Espace	Remarque
naïve	$Θ (φ^{n})$	$Θ (n)$ (pile)	recalcule les mêmes valeurs
itérative	$Θ (n)$	$Θ (1)$	ne garde que deux termes
mémoïsée	$Θ (n)$	$Θ (n)$	garde tout le tableau

Ce que l'exercice éprouve. À $n = 35$ , la version naïve fait $29860703$ appels et la mémoïsée $69$ : un facteur $430000$ , pour le même algorithme mathématique. La différence n'est pas dans la formule de récurrence, elle est dans la façon de la parcourir. C'est le sujet entier du chapitre chap:dynamique.

Et la version itérative bat la mémoïsée en espace : elle n'a pas besoin de conserver les $n$ valeurs, seulement les deux dernières. Quand le graphe des dépendances est aussi simple, la mémoïsation est un luxe.

Énoncé

Corrigé

Exercices semblables