Discussion :

[nahnouh]

Bonjour,

Je travaille sur l'algorithme de PPCM et je dois indiquer la complexité de ma proposition. Actuellement je bloque sur la complexite de la boucle :

Code :

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

1
2
3
4
5
while(b != 0){
   	x = a%b;
	a = b;
	b = x;
   }

Merci d'avance pour votre aide

[Invité]

Se trouve dans toutes les bonnes librairies: http://fr.wikipedia.org/wiki/Algorit...son_exactitude

[nahnouh]

Navrée, mais j'ai pas compris ta réponse. Mon problème n'est pas de réinveter la roue, je travail sur un plus grand algo mais j'ai besoin d'utiliser le PPCM et pour monter que ma proposition est bonne je dois calculer sa complexité et je donc j'ai besoin de celle du PPCM. J'ai touvé sur internet des codes tout prêt et je dois calculer la complexité de celui que j'ai pris et je bloque sur celle de cette boucle while.

J'espère que je suis plus claire ;-)

[Invité]

C'est donné par le théorème de Lamé: O(log(b))

[nahnouh]

Merci beaucoup et désolé ;-)