Trois Fibonacci, trois complexités

Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 3 — Algorithmes, programmes et complexité

Énoncé

Comparer, en temps et en espace, ces trois façons de calculer $F_{n}$ : la récursion naïve, l'itération, et la récursion mémoïsée. Compter les appels.

Corrigé


/* (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.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.