Methode pour trouver la complexité d'algorithmes

**line86** · 28/06/2007, 21h09

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** · 29/06/2007, 09h35

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** · 29/06/2007, 09h53

Envoyé par 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

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** · 29/06/2007, 10h07

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** · 29/06/2007, 10h14

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

**landryx** · 29/06/2007, 10h32

Envoyé par line86

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** · 29/06/2007, 11h30

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.

**kromartien** · 29/06/2007, 11h55

bien sûr. dire c'est en O(n) n'est d'aucune utilité ici. Aucun rapport avec la question posée. L'exercice ici consiste simplement à dénombrer les itérations successives équivalent chacunes à un affichage de '*' .

le n² est juste seulement pour une boucle de type

Code :

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

1
2
3
 
for (i=1,i<n,i++)
   for(j=1;j<n;j++)

Ici l'algo est volontairement compliqué dans le but de faire parvenir l'élève à un dénombrement strictement calculatoire du nombre d'itérations successives (cf l'expression formelle donnée dans mon dernier poste qui n'est peut être pas bonne je ne suis pas certain de sa validité)

Après la finalité j'imagine que ça doit être de prouver la convergence de telle ou telle suite. Bien du courage

**landryx** · 29/06/2007, 12h46

Ha..Je l'avais pas compris comme ça!!^^...

**ol9245** · 29/06/2007, 17h22

il a quand même parlé de complexité, pas de dénombrement. Pour calculer la complexité, je connais pas la méthode officielle. Moi je me dirait que N étant déja très grand, que se passe-t-il quand je double la valeur de N

une boucle for(i=0 ; i<n ; ++i) double si n double -> je suis dans O(N)
une boucle for(i=j ; i<n ; ++i) double aussi -> O(N)
une boucle for (i=0 ; i*i<n ; ++i) augmente de racine (2) si n double. -> je suis dans O(racine (N))

et ainsi de suite.

quand j'ai la compleexité de chaque boucle, la complexité totale est le produit des complexités des boucles imbriquées.

[hors sujet] ya pas assez de problème intéressants dans la vraie vie pour aller chercher des énoncés exos chez les martiens ? (mes deux grains de sel)

**PRomu@ld** · 29/06/2007, 20h28

[hors sujet] ya pas assez de problème intéressants dans la vraie vie pour aller chercher des énoncés exos chez les martiens ? (mes deux grains de sel)

Il y a énormément de problèmes de tous les jours (en entreprise), où tu peux trouver des complexités de cet acabit.

il a quand même parlé de complexité, pas de dénombrement

Parfois, tu as besoin de savoir exactement le nombre d'itération en fonction de n, et pas une borne sup comme te la donne la notation grand o (c'est la notation theta). Ca peut être intéressant suivant le type d'application (si tu fais tu temps réel par exemple).

**kromartien** · 29/06/2007, 22h46

C'est calculable, c'est dénombrable formellement, autant le faire plutôt que de donner des approximations majorations/minorations. Ici le mieux n'est pas l'ennemi du bien.

Avoir une indication théorique c'est bien mais qiand le nombre d'itérations est déterminé, je ne vois pas ce qui empêcherait de le calculer, et surtout pourquoi il ne faudrait pas le faire. La compléxité d'un algo pour moi c'est le nombre d'itérations successives enfin en tous cas d'après le problème tel qu'il est posé ici.

Sinon je ne vois pas trop le sens de la question.

**PRomu@ld** · 30/06/2007, 08h41

La compléxité d'un algo pour moi c'est le nombre d'itérations successives enfin en tous cas d'après le problème tel qu'il est posé ici.

Ca n'est pas toujours facile ou possible, si tu as un algo qui utilise une heuristique, la complexité est souvent difficile à évaluer (par ex Kruskall avec compression des chemins). C'est pour celà qu'on est amené à utiliser des approximations mais je suis tout à fait d'accord pour évaluer directement la complexité dans le cas que nous avons ici.

**ol9245** · 30/06/2007, 10h33

wiki, toute relative que soit la fiabilité de cette source est d'accord avec moi :
"On étudie systématiquement la complexité asymptotique, notée grâce aux notations de Landau.
* idée 1 : évaluer l'algorithme sur des données de grande taille. Par exemple, lorsque n est 'grand', 3n3 + 2n2 est essentiellement 3n3.
* idée 2 : on élimine les constantes multiplicatrices, car deux ordinateurs de puissances différentes diffèrent en temps d'exécution par une constante multiplicatrice. De 3 * n3, on ne retient que n3"
l'article reconnait ensuite les limites de l'approche, tout en défendant sa nécessité.

Est-ce que donc, par hazard, cet exo n'aurait pas, entre autres buts, celui de faire comprendre que

Code :

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

1
2
3
4
5
pour i=1 à n ; 
pour j=i à n ;
...
suivant ;
suivant ;

a la même complexité algorithmique que

Code :

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

1
2
3
4
5
pour i=1 à n ; 
pour j=1 à n ;
...
suivant ;
suivant ;

quand aux autres boucles genre

Code :

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

for (i=0 ; i*i < n ; ++i)

au risque d'être contredit, je persiste à les qualifier de loufoques. je dirais même que ce n'est pas une bonne idée de faire travailler des étudiants sur du code comme ça, car il déroge à une règle d'or : La priorité n°1 d'un code est sa lisibilité. Et des boucles exotiques de ce tonneau, pour moi, c'est du charabia, juste bon pour la poubelle.

**PRomu@ld** · 30/06/2007, 10h43

au risque d'être contredit, je persiste à les qualifier de loufoques. je dirais même que ce n'est pas une bonne idée de faire travailler des étudiants sur du code comme ça, car il déroge à une règle d'or : La priorité n°1 d'un code est sa lisibilité. Et des boucles exotiques de ce tonneau, pour moi, c'est du charabia, juste bon pour la poubelle.

Encore une fois, je le répète, il arrive que dans la vie de tous les jours, on ait recours à ce genre de méthodes, avoir un monde idéaliste où toutes les boucles commencent à 1 et finissent à n n'est que pure utopie, la lisibilité du code n'est absolument pas en cause.

**ol9245** · 30/06/2007, 14h09

Loin de moi l'esprit de polémique, surtout avec le responsable de la rubrique

(que je respecte infiniment d'ailleurs

pour son dévouement au forum et la qualité de ses interventions. Les choses les plus simples sont toujours bonns à dire).

Juste dire ici ce que quelqu'un d'autre m'a dit il y a bien longtemps, et que je n'ai jamais oublié tellement ça m'a guidé dans mon travail quotidien :

Q : à quoi sert un code source ?
R : un code source sert avant tout à être lu.
Q : quelles est la qualité la plus importante d'un code source ?
R : la qualité la plus importante d'un code source est sa lisibilité

Q : à quoi sert un exécutable
R : un exécutable sert à être exécuté. Personne ne lit un exécutable.

Q : à quoi sert un compilateur ?
R : un compilateur sert à transformer qqchose de lisible, mais non fonctionnel, en qqchose de fonctionnel, mais non lisible.

Si personne n'avait besoin de lire les codes sources, on programmerait tous directement en langage machine ou en asembleur. Si les langages existent, c'sest parcequ'on a besoin de lire ce qu'on écrit. c'est pas plus compliqué que ça.

Maintenant, chacun fait comme il le sent. La lisibilité est une notion assez relative et personnelle. Dans le feu de l'action, on peut être capable de relire des trucs un peu "space" qu'on vient d'écrire. Avec l'expérience, on sait repérer, et réécrire, les morceaux de code qui seront devenus opaques après 3 mois de sédimentation. C'est à force de me gratter la tête sur des pages et des pages de code que j'avais écrites 3 mois avant que j'ai compris ce que ce mec voulait me dire.

"Comme on fait son lit on se couche" dit l'adage. Chacun a 99% de chances d'être le prochain lecteur des lignes de code qu'il écrit. Et on a 99% de chance d'être amené tôt ou tard à relire son propre code.

enfin, dernier point : la compacité d'un code n'est pas un critère de lisibilité. Ca y contribue, dans une certaine msure, pas plus que ça.
La capacité d'un langage à permettre de décrire des procédure complexes de manière compacte et lisible, là, oui, ça c'est une qualité (du langage, pas du code).

OL

**pseudocode** · 30/06/2007, 14h15

@ol9245: a 100% d'accord

**PRomu@ld** · 30/06/2007, 14h30

Loin de moi l'esprit de polémique, surtout avec le responsable de la rubrique (que je respecte infiniment d'ailleurs pour son dévouement au forum et la qualité de ses interventions. Les choses les plus simples sont toujours bonns à dire).

Arrêtons les fleurs ...

Je suis tout à fait d'accord avec ton intervention, visiblement nous ne nous sommes pas tout à fait compris, le fait que la boucle soit exotique n'est pas un problème en soit et ça ne remet pas toujours en cause la lisibilité. A mon avis pour rendre un code source lisible les commentaire y sont pour beaucoup (ça fait 80-90% du boulot à mon avis).

Ma remarque faisait état de ta boucle :

Code :

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

for (i=0 ; i*i < n ; ++i)

Ce genre de boucle peut arriver dans la vie de tous les jours.

**ol9245** · 30/06/2007, 15h50

Code :

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

1
2
3
4
int racine_de_n = (int)sqrt(n) ;
for (i=0 ; i<racine_de_n ; ++i) {
...
}

**PRomu@ld** · 30/06/2007, 15h56

J'avais bien saisi le message, il arrive dans un contexte de performance pure (j'ai eu le tord de penser que mon domaine avait énormément d'importance

) que l'on veuille limiter les opérations couteuses comme la racine carrée, et c'est pour cela que je voulais dire que les commentaires était nécessaires.

Methode pour trouver la complexité d'algorithmes

Algorithmes et structures de données

Discussions similaires

Partager

Partager