Complexité Fibonacci
Résolu
nadal1991
-
DM -
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 .
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:
- Algorithme fibonacci complexité
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Algorithme ajout rapide snapchat - Forum Snapchat
- Ajout rapide snap - Forum Snapchat
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.
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.
Pacorabanix
Messages postés
3248
Date d'inscription
Statut
Membre
Dernière intervention
663
merci beaucoup pour cette réponse complète et précise !
DM
La fonction à mémoire serait encore plus efficace. Surtout si en application on utilise une hashtable
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) )
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 ?
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 ??
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 ??
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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
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
