Complexité d'un algorithme récurrent

Bonjour,

pouvez vous m'indiquer svp :calim2: la complexité de f en nombre de multiplication :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

int f(int n){ if(n==0) return 1; else return (g(n-1)*4); }   int g(int n){ int p; if(n==0) return 1; else{ p=h(n-1); return (p*p); } }   int h(int n){ if(n==0) return 1; else return (f(n-1)*5); }

---

Merci d'avance
T.Bazoga

Nous ne sommes pas là pour faire tes devoirs ...

Indique nous ce qui te pose problème pour calculer la complexité et on pourra d'indiquer comment procéder.

OK :aie:

voila ce que je pensais,

Cf(n): nombre de multiplication réalisé par f
Cg(n): nombre de multiplication réalisé par g
Ch(n): nombre de multiplication réalisé par h

Cf(n)=1 + Cg(n-1) n>=1
Cg(n)=1 + Ch(n-1) n>=1
Ch(n)=1 + Cf(n-1) n>=1

d'où Cf(n)=3 + Cf(n-3) pour n>=3 donc comment trouvé Cf(n) en fonction de n, il me parait que Cf(n)=n mais je ne suis pas sûr ?

est ce que c'est bon maintenant :mouarf:

Merci encore une fois

En fait tu es sur la bonne voie ;)

L'idée pour le démontrer proprement est de supposer Cf(n) = O( n ) puis de procèder par un raisonnement par récurrence et le tour est joué. (ie : tu vérifie pour Cf(0), Cf(1), Cf(2), ... puis ensuite du suppose Cf(n) et tu regarde ce qu'il en est de Cf(n+1) et le tour est joué).

EDIT : Si tu veux une étude plus fine (ie Cf(n) = Sigma( ... ) et pas Cf(n) = O( ...) ) il faut que tu détailles ton analyse (pour n congru à 0 modulo 3, n congru à 1 modulo 3 et n congru à 2 modulo 3))

Une excellente référence pour le calcul de la complexité d'un algorithme récursif est le chapitre 4 intitulé "Recurrences" du livre http://algo.developpez.com/livres/#L2100039229 (déjà conseillé à bazoga et sûrement connu de PRomu@ld, mais pour les autres intéressés par le sujet ;) )

Bonjour,

effectivement, avec un raisonnement par récurrence ça marchait :ccool:
Merci pour vos réponses.:D

cdl
A.CHAFIK