Discussion :

[line86]

Bonsoir a vous tous,
voila je cherche la methode pour trouver la complexité de ces deux algo:

Code :

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

1
2
3
4
5
6
 
int i,j,k;
for (i=1;i<=n;i++)
 for (j=1,i*j<=n;j++)
  for (k=1;k<=log(i);k++)
    printf("*");

Code :

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

1
2
3
4
 
for (i=1;i*i<=n;i++)
 for (j=0;j<i;j++)
printf ("*");

merci de votre aide,
Bonne soirée

[line86]

Merci pour votre reponse,
mais le seul probleme c'est que j'essaye de trouver la complexité par la methode papier crayon... mais je ne trouve rien de bien...

Pour le premier je trouve cette suite de chiffre:
n=3 -> 1* - n=4 -> 2* - n=5 -> 3* - n=6 -> 5* - n=7 -> 6* - n=8 -> 9*

Merci encore

[landryx]

Merci pour votre reponse,
mais le seul probleme c'est que j'essaye de trouver la complexité par la methode papier crayon... mais je ne trouve rien de bien...

Pour le premier je trouve cette suite de chiffre:
n=3 -> 1* - n=4 -> 2* - n=5 -> 3* - n=6 -> 5* - n=7 -> 6* - n=8 -> 9*

Merci encore

Je comprends pas. Quel est le rapport entre la suite de nombre et la complexité que tu recherche?
la complexité pour une boucle pour est O(n). si on deux boucles imbriquées elle passe à O(n²), et ainsi de suite...

[line86]

Merci pour ta reponse

la complexité pour une boucle pour est O(n). si on deux boucles imbriquées elle passe à O(n²), et ainsi de suite

Mais le fait que ma troisieme boucle par exemple s'arretes a log(i) produit le meme effet que si elle s'arretait a n ???

[kromartien]

Non bien sûr que non c'est trop simplifier le problème.

[landryx]

Merci pour ta reponse



Mais le fait que ma troisieme boucle par exemple s'arretes a log(i) produit le meme effet que si elle s'arretait a n ???

raisonne que pour chaque pour chaque i tu vas aller de k a log(i).donc tu vas aller n fois de k vers log(i).

[PRomu@ld]

la complexité pour une boucle pour est O(n). si on deux boucles imbriquées elle passe à O(n²), et ainsi de suite...

Ca c'est la méthode très large, tu peux même dire qu'une boucle est dans O(n!), ça reste correct mais pas forcément acceptable. Il faut faire attention aux généralités.