Discussion :

[lixtoon]

Bonjour
Depuis des jours j'essai de comprendre comment on peut calculer la complexité d'un algorithme mais je n'y arrive pas SOS SVP
MERCI ^^

[Aleph69]

Bonjour,

en première approche, il suffit de compter le nombre d'opérations (+,-,*,/). Tu obtiendras une complexité polynomiale. Si tu utilises des algorithmes plus compliqués (tris, graphes, ...) ou si tu souhaites démontrer des complexités polylogarithmiques, l'analyse est plus compliquée et dépend de ce que tu cherches à mesurer (complexité moyenne, complexité du cas le pire, etc). Il y a sûrement de très bons livres sur la question. Tu peux aussi chercher sur le net comment on démontre la complexité des algorithmes de tri ou de la fft ou d'algos de graphes pour avoir des premiers exemples.

[souviron34]

disons qu'il y a une théorie (computational complexity) : cherche et il y a l'exposé (succint) sur Wikipédia.

En gros, le calcul théorique est de donner un facteur de proportionalité par rapport au temps - ou, de manière relativement équivalente - au nombre de points considérés..

Par exemple, pour une boucle :

Code :

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

1
2
3
pour i = 0 jusqu'à i < N
   ...
fin pour

on dira qu'elle est de complexité O(N), c'est à dire qu'elle s'excute proportionnelement au nombre N.

Si maintenant on a une double boucle :

Code :

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

1
2
3
4
5
6
pour i = 0 jusqu'à i > N
   ...
   pour j = 0 jusqu'à j < M
      ....
   fin pour
fin pour

on dira qu'elle est de complexité O(N*M), car à chaque i il faut parcourir M j.

Cela donne une indication sur le temps relatif, et/ou la complexité relative..

[lixtoon]

Bonjour
bihh la ..j ai bien pigé
merci merci bcp ^^