Methode pour trouver la complexité d'algorithmes

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

Code:

---

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:

---

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

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... :oops:

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

Citation:

---

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... :oops:

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...:mouarf:

Merci pour ta reponse

Citation:

---

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

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

Citation:

---

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).

Citation:

---

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.

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:

---

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 :)

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

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)

Citation:

---

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

Citation:

---

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).

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. :koi:

Citation:

---

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.

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:

---

1 2 3 4 5

pour i=1 à n ; pour j=i à n ; ... suivant ; suivant ;

---

a la même complexité algorithmique que

Code:

---

1 2 3 4 5

pour i=1 à n ; pour j=1 à n ; ... suivant ; suivant ;

---

quand aux autres boucles genre

Code:

---

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.

Citation:

---

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.

Loin de moi l'esprit de polémique, surtout avec le responsable de la rubrique ;) (que je respecte infiniment d'ailleurs :bravo: 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

@ol9245: a 100% d'accord :chin:

Citation:

---

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 ... :oops:

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:

---

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

---

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

Code:

---

1 2 3 4

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

---

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 :aie: ) 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.

je suis totalement d'accord avec toi ol9245.. Pour une fois désolé PRomu@ld ;)

Mais je met moi aussi le code à la poubelle si je vois ça, et je ne vois aucun cas qui puiisse comme tu dis "dans la vie de tous les jours" justifier un tel comportement.

ça peut être lisible ou non, mais c'est le principe même qui est en cause.

Comme les

Code:

---

for ( i = 0 ; j < 4 , opt=opt+1, pt=pt++, dcl--, .... ; i++ )

---

...

De plus, si tu fais du code "industriel", ce n'est pas maintenable (et je ne parle pas de maintenance "à long terme", mais par exemple par quelqu'un su SAV).

Bon on s'est un peu écarté du sujet, mais c'est juste que (et ol9245 et pseudocode comme moi j'en suis certain) on a tous vu de telles horreurs qu'on est assez sensibilisé à de la belle écriture....

Compact ne veut pas dire optimisé.

Enfin dernier point sur le sujet : il est évident que lorsqu'on optimise du code dans ses derniers retranchements la lecture peut devenir ardue... Mais elle est cependant rendue plus facile si l'écriture suit certaines règles de bon sens.
L'optimisation se fait sur l'algorithme, les données, ou leur représentation, mais l'écriture de l'algorithme n'est pas touchée....

Maintenant, il est évident que calculer la complexité exacte peut être utile... Cependant dans l'écrasante majorité des cas, le calcul de complexité sert uniquement de base d'ordre de grandeur pour savoir si : 1) l'algo est efficace 2) si on augmente la machine est-ce que cela ira plus vite ? et enfin 3) donner une limite prévisionnelle du temps de calcul : 1 seconde, 1 minute, 1 heure, 1 jour, 1 semaine, 1 an... soit pour satisfaire un client, soit pour demander du temps sur une machine ultra-puissante (je me souviens qu'en thèse, sur un HP1000, j'avais à faire un Simplex sur 1000 étoiles, et j'avais calculé un an 1/2 de calcul. D'où achat d'une heure de Cray.. :D )

Citation:

---

Mais je met moi aussi le code à la poubelle si je vois ça, et je ne vois aucun cas qui puiisse comme tu dis "dans la vie de tous les jours" justifier un tel comportement.

---

Le coût d'une racine carré est un peut plus que celui d'une division qui elle est 5 fois plus lente qu'une muliplication (en terme de cycle processeur).

Comme je l'ai dis, je me suis enflamé lorsque j'ai dis tous les jours mais ce genre de trucs je le fais quasi-quotidiennement (accompagné d'une dose de commentaires conséquents). J'ai eu tord de généraliser mon propre cas, excusez-moi ... :hola:

Citation:

---

Compact ne veut pas dire optimisé

---

.

Ca n'est absolument pas ce que j'ai dis.

Citation:

---

on a tous vu de telles horreurs qu'on est assez sensibilisé à de la belle écriture....

---

absolument d'accord. Sorti de mon domaine, je suis relativement pointilleux là dessus.

Citation:

---

Envoyé par PRomu@ld

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 :aie: ) 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.

---

Code:

---

1 2 3

for (i=0 ; i*i < n ; ++i) { ... }

---

Code:

---

1 2 3 4

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

---

C'est sur, pour les performances, il vaut mieux se taper une multiplication a chaque tour de boucle, plutot que de calculer une seule fois une racine carrée... :aie:

:dehors:

Bon, il est vrai qu'ici, c'est pas très judicieux.:aie: (même ridicule)

Mais je suis convaincu qu'une écriture parfois moins claire permet d'améliorer les performances.

A titre d'exemple, je fais de la synthèse d'image, je passe d'une image générée en un peu moins de 10 secondes à presque 6-7 images par secondes (et presque une vingtaine avec des instuctions SSE). l'algorithme utilisé étant scrupuleusement le même, la complexité est la même.

Oui, mais dans ton cas il s'agit d'optimisation d'implémentation, et pas d'optimisation d'algorithme. Effectivement dans ces cas la, tu peux ecrire du code "moins optimal" en sachant que le compilateur (ou le hardware) accelerera le traitement.

Ca me rappelle la glorieuse epoque du codage des "Demos" en assembleur sur Atari où, pour faire defiler 100 etoiles (=100 pixels), il etait plus performant de dupliquer 100 fois une ligne plutot que de faire une boucle. :aie: 8O


PS: Je m'en voudrait de dire au responsable de la rubrique (:hola:) qu'il participe a faire partir ce thread en total hors-sujet....Donc je le dirais rien :mrgreen:

Citation:

---

PS: Je m'en voudrait de dire au responsable de la rubrique () qu'il participe a faire partir ce thread en total hors-sujet....Donc je le dirais rien

---

Oui, c'est le week-end, il y a un peu de relachement :aie: , d'autant plus que je fais la chasse à ce genre de pratique. Je suis désolé :hola:.

Et puis c'était pas totalement hors-sujet, ça montre que la complexité n'est qu'une indication et qu'elle ne reflète pas forcément la réalité. Entre deux algorithmes en O(n log n) il peut exister des différences notables en pratique (du fait des constantes cachées)