Complexité Fibonacci
Résolu
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 .
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 .
Configuration: Windows XP Firefox 3.0.15
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. -
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) ) -
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 !!
-
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-
-
@fslpardon a(n)=f(n+1)-1
-
-
une reponse silvouplait
merci -
une reponse silvouplait
-
une reponse s'il vous plait
