Complexité Fibonacci

Résolu/Fermé
nadal1991 - 5 déc. 2009 à 10:08
 DM - 6 oct. 2010 à 01:18
Bonjour,
voila j'ai un problème dans le chapitre des complexité des algorithme , et si quelqu'un pouvais m'aider avec cette exercice ça m'aiderai a comprendre :
le nombre de Fibonacci Fib(n) Est définie :

Fib(0)=1 ; Fib(1)=1; Fib(n)= Fib(n-1) + Fib(n-2) ;

l'algorithme récursif :

fibo(n)
Si (n=0)ou(n=1) alors
return 1 ;
sinon
return fibo(n-1) + fibo(n-2) ;
fin .

1* évaluer sa complexité pratique et en déduire sa complexité asymptotique ?

Merci d'avance .
A voir également:

13 réponses

Soit u, le nombre d'or et v = 1-u. Alors la complexité (algébrique!) de votre algorithme est C(n) = F(n+1)-1=-1+( u^(n+1)-v^(n+1))/sqrt(5). Donc pour 'grand' n, C(n) = O((1/sqrt(5)).u^(n+1)) car la deuxième terme devient de la pousière. Cette complexité subit une explosion exponentielle. En faite, votre implementation est très naive (vous calculez et recalculez des choses à la volé!). Quitte à utiliser des 'buffers' pour y mettre tes 'grains' consécutifs. comme ça (en maple, par exemple ...) :

fib := proc (n) local j, x, y, z;
x := 0; y := 1;
if n <= 0 then return n end if;
for j from 1 to n-1 do
z := x+y; x := y; y := z
end do; return z
end proc

La complexité est cette fois-ci O(n), donc linéaire !
Plus 'enervant', en remarquant que F(n+k+1)=F(n)F(k)+F(k+1)F(n+1), faites-en un algorithme avec complexité O(log(n)), donc sous-linéaire !

My french is not very good; please forgive me.
Bon courage.
10
Pacorabanix Messages postés 3248 Date d'inscription jeudi 23 août 2007 Statut Membre Dernière intervention 19 mai 2013 661
22 févr. 2010 à 22:20
merci beaucoup pour cette réponse complète et précise !
0
La fonction à mémoire serait encore plus efficace. Surtout si en application on utilise une hashtable
0