Proposition de solution

>>> suitefibo(10)
Fibo(1) = 1
Fibo(2) = 1
Fibo(3) = 2
Fibo(4) = 3
Fibo(5) = 5
Fibo(6) = 8
Fibo(7) = 13
Fibo(8) = 21
Fibo(9) = 34
Fibo(10) = 55

Cette fonction calcule le n-ième terme de la suite de Fibonacci de façon récursive.

>>> run (5, fiborec)
Fibonacci(5)
  Fibonacci(4)
    Fibonacci(3)
      Fibonacci(2)
        Fibonacci(1)
        Fibonacci(0)
      Fibonacci(1)
    Fibonacci(2)
      Fibonacci(1)
      Fibonacci(0)
  Fibonacci(3)
    Fibonacci(2)
      Fibonacci(1)
      Fibonacci(0)
    Fibonacci(1)
Fibo(5) = 5
Complexité : 15

On voit les appels de fonctions :

• Fibonacci(5) appelle Fibonacci(4) et Fibonacci(3).
• Fibonacci(4) appelle Fibonacci(3) et Fibonacci(2).
• …

On remarque que Fibonacci(k) est calculé à plusieurs reprises, ce qui est inéfficient.

Pour calculer la complexité (en temps de calcul), on dénombre le nombre d’exécution / d’appels de la fonction _fiborec. A partir de 9, la complexité est supérieure à n²

Cette fonction calcule le n-ième terme de la suite de Fibonacci de façon récursive, mais contrairement à la version précédente, les valeurs calculées sont mémorisées.

>>> run (5, fibomemo)
Fibonacci(5)
  Fibonacci(4)
    Fibonacci(3)
      Fibonacci(2)
        Fibonacci(1)
        Fibonacci(0)
Fibo(5) = 5
Complexité : 6

On voit les appels de fonctions : Fibonacci(5) appelle Fibonacci(4) et Fibonacci(3). Seulement, Fibonacci(3) aura déjà été calculé lors de l’appel de Fibonacci(4)…

On remarque que Fibonacci(k) est calculé une seule fois.

Pour calculer la complexité (en temps de calcul), on dénombre le nombre d’exécution / d’appels de la fonction _fibomemo. Ici, grâce à la mémorisation des valeurs calculées, la complexité est un O(n).

La mémorisation coûte un dictionnaire de n clés, soit une complexité mémoire (spatiale) en O(n).

Cette solution illustre le concept de compromis temps-mémoire.

Cette fonction calcule le n-ième terme de la suite de Fibonacci de façon itérative.

>>> run (5, fiboite)
Fibonacci(0)
Fibonacci(1)
Fibonacci(2)
Fibonacci(3)
Fibonacci(4)
Fibonacci(5)
Fibo(5) = 5
Complexité : 6

Pour calculer la complexité (en temps de calcul), on dénombre le nombre d’itérations (n). On est en O(n).

Le coût mémoire ne dépend pas de la tailles des données (le calcul utilise toujours 3 variables de type entier). La complexité en mémoire est en 0(1).

C’est la solution la plus efficace à la fois en temps de calcul et en coût mémoire.