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.