Discussion :

[gmatu]

on a comme fonctions :

Code :

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

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 :

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

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 :

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

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 :

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

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

[Franck Dernoncourt]

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 :

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

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)

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

Code :

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

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

[gmatu]

Merci de cette réponse,

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

Code :

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

 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

[Franck Dernoncourt]

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.

[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 ?

par avance merci,
GM

[gmatu]

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 :

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

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