Discussion :

[bazoga]

Bonjour,

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[PRomu@ld]

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.

[bazoga]

OK

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

Merci encore une fois

[PRomu@ld]

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

[Franck Dernoncourt]

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 )

[bazoga]

Bonjour,

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

cdl
A.CHAFIK