Chiffrer le gaspillage

Notons $A(n)$ le nombre d'appels de la version naïve. Un appel se fait lui-même, puis lance $A(n-1)$ et $A(n-2)$ appels :

$$A(0)=A(1)=1,A(n)=1+A(n-1)+A(n-2).$$

On vérifie par récurrence double que $A(n)=2F_{n+1}-1$, où $F$ est la suite de Fibonacci : c'est vrai pour $n=0$ et $n=1$, et $A(n)=1+(2F_n-1)+(2F_{n-1}-1)=2(F_n+F_{n-1})-1=2F_{n+1}-1$.

Mesure (compteur incrémenté à chaque appel) :

n=10  fib=      55  appels naif=      177  appels memoise= 19
n=20  fib=    6765  appels naif=    21891  appels memoise= 39
n=30  fib=  832040  appels naif=  2692537  appels memoise= 59

On lit bien $A(30)=2\times 1346269-1=2692537$, et $A(40)=2F_{41}-1=331160281$ : le « milliard » du chapitre est un ordre de grandeur, la valeur exacte est trois cent trente et un millions.

Côté mémoïsation, la mesure donne $19,39,59$ : c'est $2n-1$. Pourquoi $2n-1$ et non $n$ : chaque valeur $k$ entre $2$ et $n$ est calculée une fois, mais elle est demandée deux fois — une fois par $k+1$, une fois par $k+2$. Le second appel trouve la table garnie et rend immédiatement : il coûte $O(1)$, mais il compte comme appel. La complexité reste $\Theta (n)$.

Ce que l'exercice montre : le chevauchement des sous-problèmes n'est pas une figure de style. Ici il fait passer de $\Theta ({\phi }^n)$ à $\Theta (n)$, et le rapport vaut déjà $45000$ pour $n=30$.