Un point m'embête dans ton implémentation de la suite : chaque appel de la fonction appelle 2 instances supplémentaires, qui se résolvent récursivement, donc qui restent en attente jusqu'à ce que toutes les instances aient atteint 0 ou 1. Alors ça marche sans trop de problèmes pour fib(5) ou fib(7), mais essaie de calculer fib(24) et tu vas beaucoup moins rigoler. En effet, cette implémentation appelle de l'ordre de 2^n instances de la fonction. Le problème étant que quand tu écris :
int => fib(n - 1) + fib(n - 2),
tu ne gardes pas en réutilises pas le résultat de fib(n-2) pour calculer fib(n-1) : tu appelles une nouvelle instance toute neuve. Une solution est d'avoir un objet de type tuple, indiçable et de faire retourner un tuple à ta fonction :
# Complexité algorithmique
Posté par Liorel . En réponse au journal [Letlang] Hommage à Leonardo Pisano Fibonacci. Évalué à 3.
Un point m'embête dans ton implémentation de la suite : chaque appel de la fonction appelle 2 instances supplémentaires, qui se résolvent récursivement, donc qui restent en attente jusqu'à ce que toutes les instances aient atteint 0 ou 1. Alors ça marche sans trop de problèmes pour
fib(5)oufib(7), mais essaie de calculerfib(24)et tu vas beaucoup moins rigoler. En effet, cette implémentation appelle de l'ordre de2^ninstances de la fonction. Le problème étant que quand tu écris :tu ne gardes pas en réutilises pas le résultat de
fib(n-2)pour calculerfib(n-1): tu appelles une nouvelle instance toute neuve. Une solution est d'avoir un objet de type tuple, indiçable et de faire retourner un tuple à ta fonction :Ainsi, tu n'appelles ta fonction qu'une seule fois par instance, et ton temps de calcul progresse désormais en O(n) et non en O(2n).
Ça, ce sont les sources. Le mouton que tu veux est dedans.