Complexité dans des fonctions imbriquées

on a comme fonctions :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int f_Appel_g (int n){ if((n == 0) ||(n == 1)) return (1); else return g_Appel_f(g(n-2)); }   int g_Appel_f (int n){ if((n = 0)) return (1); else return (f_Appel_g (f(n - 1)*f_Appel_g (n - 1)); }

---

S'il faut chercher la complexité de f_Appel_g en nbre de multiplication.
je commence à chercher le nbre de multiplication dans chaque fonction:
f_Appel_g :

Code:

---

1 2	si n = 0 ou n= 1, C f_Appel_g (n) = 0 si n > 1 C f_Appel_g (n) = C g_Appel_f (n -2)

---

et pour g_Appel_f

Code:

---

1 2	si n = 0, C g_Appel_f (0) = 0 si n > 0 C g_Appel_f (n) = 1 + 2 C f_Appel_g (n -1)

---

mon souci est comment relier les deux relations, on a le droit d'écrire :

Code:

---

1 2 3

si n <= 2 , C f_Appel_g (n) = 0 si n > 2 C f_Appel_g (n) = 1 + 2 C f_Appel_g (n -3)

---

merci d'avance,
GM

Citation:

---

Envoyé par gmatu

S'il faut chercher la complexité de f_Appel_g en nbre de multiplication.
je commence à chercher le nbre de multiplication dans chaque fonction:
f_Appel_g :

Code:

---

1 2	si n = 0 ou n= 1, C f_Appel_g (n) = 0 si n > 1 C f_Appel_g (n) = C g_Appel_f (n -2)

---

---

Oui ssi f = O(1) et g = O(1)

Citation:

---

Envoyé par gmatu

mon souci est comment relier les deux relations, on a le droit d'écrire :

Code:

---

1 2 3

si n <= 2 , C f_Appel_g (n) = 0 si n > 2 C f_Appel_g (n) = 1 + 2 C f_Appel_g (n -3)

---

---

Tout à fait, c'est ainsi que sont analysées les complexités des fonctions récurrentes. Pour plus de détails, direction http://algo.developpez.com/livres/#L2100039229 chapitre 4 et http://en.wikipedia.org/wiki/Master_theorem

Merci de cette réponse,

donc on peut en déduire si je ne me trompe que :

Code:

---

pour tout n, f_Appel_g (n) = n/3

---

pour la démonstration de cette formule il faut faire une récurrence en s'appuyant sur les modulo (3 si j'ai encore quelques notions)?

par avance merci
GM

Je dirais que C f_Appel_g (n) = 1 + 2 C f_Appel_g (n -3) est immédiat (même si je n'ai pas vérifié si la relation était bonne) car il suffit de "déplier" un peu la fonction, donc pas besoin de démonstration.

Ensuite, pour prouver la complexité de C f_Appel_g (n), cf les deux références de mon message précédent.

merci, mais J'ai regardé la page en anglais "master theorem" avec la formule de Cormen ...,
je ne vois pas comment cela peut coller avec ma formule? Elle n'est pas de la forme (n/b) OK on peut prendre b=1 mais il faut que je la modifie forcément alors pour "isoler" n, non ?

par avance merci,
GM

Je n'ai pas réussi à utiliser les formules proposées dans le lien indiqué, je tente une solution mais pas sûre du coup que cela soit valable pour le calcul de la complexité :

Code:

---

1 2 3 4 5 6

n-3 on a Sigma 2^i = (2 ^n/3) – 1. i=0   On en déduit que l’algorithme est en Théta(2^n/3) ?

---

par avance merci
GM

Citation:

---

Envoyé par gmatu

merci, mais J'ai regardé la page en anglais "master theorem" avec la formule de Cormen ...,
je ne vois pas comment cela peut coller avec ma formule? Elle n'est pas de la forme (n/b) OK on peut prendre b=1 mais il faut que je la modifie forcément alors pour "isoler" n, non ?

---

Oops, désolé tu as raison, j'oubliais que le master theorem ne s'applique qu'aux divide and conquer algorithms :

Citation:

---

In the analysis of algorithms, the master theorem provides a cookbook solution in asymptotic terms (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms

---

(Source: http://en.wikipedia.org/wiki/Master_theorem)

Juste pour clarifier, quelles sont les définitions des fonctions f et g ?

les définitions des fonctions f et g sont celles ci:
avec f = f_Appel_g et g = g_Appel_f

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

int f_Appel_g (int n){ if((n == 0) ||(n == 1)) return (1); else return g_Appel_f(g(n-2)); }   int g_Appel_f (int n){ if((n = 0)) return (1); else return (f_Appel_g (f(n - 1)*f_Appel_g (n - 1)); }

---

Bien vu, la complexité est effectivement Θ(2^(n/3)) à mon avis (toute vérification est la bienvenue !).

Pour vérifier ce que j'avais trouvé théoriquement et qui correspondait à ce que tu avais trouvé, j'ai fait tourner le code :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <iostream> using namespace std;   // declaring functions prototypes int f_Appel_g (int n); int g_Appel_f (int n);   int f_Appel_g (int n){ cout << "f"; if ((n == 0) ||(n == 1)) return (1); else return g_Appel_f(g_Appel_f(n-2)); }   int g_Appel_f (int n){ cout << "g"; if (n == 0) { return (1); } else { return (f_Appel_g (f_Appel_g(n - 1)*f_Appel_g (n - 1))); } }     int main() { cout << "start" << endl; cout << f_Appel_g(30) << endl; cin.get(); return 0; }

---

Les résultats sont :
n -> nb of function calls
10 -> 57
30 -> 8185
50 -> 851961

ce qui correspond approximativement à du Θ(2^(n/3)).

Bonjour,

merci beaucoup de votre aide et de vos éclaircissements, je vais essayer de trouver un exemple de même type mais permettant d'utiliser les liens mis en avant.
GM