Complexité Fibonacci [Résolu/Fermé]

Signaler
-
 DM -
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 .

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.
9
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 63000 internautes nous ont dit merci ce mois-ci

Messages postés
3241
Date d'inscription
jeudi 23 août 2007
Statut
Membre
Dernière intervention
19 mai 2013
587
merci beaucoup pour cette réponse complète et précise !
La fonction à mémoire serait encore plus efficace. Surtout si en application on utilise une hashtable
Messages postés
3241
Date d'inscription
jeudi 23 août 2007
Statut
Membre
Dernière intervention
19 mai 2013
587
oui la relation par rapport à n n'est pas évidente.

Maintenant que tu as fait tes exemples (et il il me semble que tu t'es trompé un poil), on remarque quelque chose :

lorsque tu appelles fib(n), tu fais toutes les étapes de fib(n-1) + les étapes de fib(n-2) (+ l'appel lui même à fib(n) qu'il faut compter)


fib(0) -> 1 (direct (un appel))
fib(1) -> 1 (direct (un appel))
fib(2) -> 1+1 +1 = 3
fib(3) -> 3+1 + 1 = 5
fib(4) -> 3+5 + 1 = 9
fib(5) -> 9+5 + 1 = 15
fib(6) -> 9+15 + 1= 25
fib(7) -> 15 + 25 +1 = 41
fib(8) -> 25+41 + 1 = 67
fib(9) -> 41+67 + 1 = 109

Note : je peux me tromper, surtout sur ce +1, je ne suis pas tout à fait sur non plus

le nombre d'appel a(n) à fib est donc défini par une relation de récurrence ( a(n) = a(n-1) + a(n-2) + 1 )

maintenant, c'est des maths : il faut trouver quelle est la fonction solution.

Je ne sais pas comment tu as appris en maths à résoudre ça.

On peut simplifier en disant que, asymptotiquement, le +1 est négligeable.

(résoudre a(n) =~ a(n-1) + a(n-2) )
Messages postés
3241
Date d'inscription
jeudi 23 août 2007
Statut
Membre
Dernière intervention
19 mai 2013
587
dans la charte ainsi que dans : Demander de l'aide pour vos exercices sur CCM


il est précisé qu'il est permis de faire remonter son sujet une fois par 24h, les autres internautes ne sont pas à votre service personnel constamment !


Et sinon, avez-vous fait un essai vous-même (EX: appliquer l'algorithme soi même avec un papier et un crayon et compter combien d'opérations sont effectuées (ou simplement combien d'appels à Fib) pour certaines valeurs de n (1, 2, 3, 4 ,5 , et plus si vous êtes courageux...) et qu'obtenez-vous comme nombre ?
ben voila ce que j'ai trouver :

pour n=2 on trouve 2 appel
n=3 ====> 4 appel
n=4====> 8 appel
n=5====> 14 appel

mais je vois pas de relation en fonction de n ??
silvouplait j'en ai vraiment besoin .
une réponse silvouplait

merci.
une reponse s'il vous plait
est ce quelqu'un pourrait me répondre merci !!
Messages postés
271
Date d'inscription
mercredi 5 septembre 2007
Statut
Membre
Dernière intervention
2 octobre 2011
11
rebonjour a tous ;

je voulais juste revenir sur ce topic que j'avais precedement cree pour redemander un renseignement afin de savoir si pour dans le calcul du nombre d'appel de l'algo récursif de Fibonacci on compte l'appel a f(n) ce qui induira donc que pour f(1) on aura un appel et pour f(0) on aussi un appel ou si au contraire on ne les compte pas! Merci .

et sinon je voudrai vraiment que quelqu'un m'aide pour le calcul du" nombre d'appel de la procedure Recur ;"dans cette algorithme ceci pour ma comprehension voila l'algo :

procedure recur(n,d,a;i) ;
si n=1 alor
deplacement d ver a ;
sinon debut
recur(n-1,d,i,a) ;
deplacement d vers a ;
recur(n-1,i,a,d);
fsi;
fsi;
fin.

merci beaucoup d'avance
une reponse s'il vous plait !
merci
Vous pouvez remarquer que
a(n)=f(n+)-1 avec a(n) est le nombre d'addition effectue par votre algorithme.
Puis tu peux deduire la complexite a partir de a(n)
pardon a(n)=f(n+1)-1
Messages postés
271
Date d'inscription
mercredi 5 septembre 2007
Statut
Membre
Dernière intervention
2 octobre 2011
11
une reponse silvouplait
merci
Messages postés
271
Date d'inscription
mercredi 5 septembre 2007
Statut
Membre
Dernière intervention
2 octobre 2011
11
une reponse silvouplait
Messages postés
271
Date d'inscription
mercredi 5 septembre 2007
Statut
Membre
Dernière intervention
2 octobre 2011
11
une reponse s'il vous plait