Complexité Fibonacci [Résolu]

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.

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 ?

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) )

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 !!

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 ??

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

une reponse silvouplait
merci

une reponse silvouplait

une reponse s'il vous plait