Mesurer le chevauchement

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 18 — La programmation dynamique

Énoncé

Instrumenter les fonctions de Fibonacci naïve et mémoïsée pour compter le nombre d'appels récursifs effectués. Donner les valeurs des compteurs pour $n = 10$ , $20$ et $30$ . En déduire leurs lois de croissance respectives.

Corrigé

def fib_compte(n, compteur):
    compteur[0] += 1
    if n <= 1:
        return n
    return fib_compte(n - 1, compteur) + fib_compte(n - 2, compteur)

Nombres d'appels mesurés :
Pour $n = 10$ : version naïve $= 177$ appels, version mémoïsée $= 19$ appels.
Pour $n = 20$ : version naïve $= 21891$ appels, version mémoïsée $= 39$ appels.
Pour $n = 30$ : version naïve $= 2692537$ appels, version mémoïsée $= 59$ appels.
Lois de croissance : La version naïve suit une croissance exponentielle proportionnelle à $Φ^{n}$ (où $Φ \approx 1.618$ est le nombre d'or). La version mémoïsée présente une croissance linéaire valant exactement $2 n - 1$ appels. Pour $n = 30$ , l'approche mémoïsée est environ $45000$ fois plus rapide.

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.