Suite de Fibonacci (compléxité de l'algo...)

Bonjour l'ami;

On ce cas on fait apel a la démenstration par récurrence donc tu suit les étape suivantes:

On a la propriété suivante : nombre d'additions effectuer par l'algo a(n)= F(n+1)-1;

1) on montre que cette propriété est vérifiée pour n=0 et n=1;

n=0: a(0)=F(1)-1=0 ==> vérifiée
n=1: a(1)=F(2)-1=F(1)+F(0)-1=0 ==> vérifiée,

2) on suppose que propriété est verifiée à l'ordre n (c-à-d a(n) vérifiée ) et on montre quelle est vérifiée auusi pour n+1,
donc: pour n : a(n)=F(n+1)-1 ==> vérifiée;

pour n+1: a(n+1)= F((n+1)+1)-1
.......
=a(n)+F(n) comme a(n) est vérifiée donc a(n+1) est vérifiée.

complexité de l'algo est de l'ordre de F(n+1);

pour l'algo itératif essai d'utiliser la question précédente :-*)

Bon courage.

merci de votre aide
mais le question 2 vous pouvez m'expliquer , parce que j'ai pas bien compris compléxité de l'algo recursif
et quesition 3 aussi

merci bcp

Pour l'algorithme va voir ici