Discussion :

[logo98]

salut,

je voudrais savoir comment déterminer la complexité d'un algorithme quelconque et peut-on dire que cette dernière peut être un indice de performance d'un algorithme par rapport à un autre ou bien il faut chercher un autre critère pour comparer deux algorithmes (par exemple le temps d'exécution)?
Excusez moi mon ignorance et merci d'avance pour votre explication.

[FR119492]

Salut!
Les modérateurs qui interviennent sur ce forum sont pour une part des algorithmiciens pour lesquels le critère essentiel est la complexité, et, pour une autre part, des numéristes comme moi pour lesquels il n'y a que le temps de calcul qui compte. Dans beaucoup de domaines, les deux critères sont équivalents, mais il y a des exceptions. Alors, à toi de choisir.
Jean-Marc Blanc

[lcfseth]

La compléxité d'un algorithm décrit le comportement de ce dernier en fonction de ces entrées ( le fameux n ).
Un algo en O(n) est un algorithm dont le temp d'execution croit de facon lineaire par rapport au nombre d'entrées. Un algo en O(n²) croit de facon lineaire par rapport au carré de ce nombre. Bien sur, un algo en O(n²) est plus lent qu'un algo en O(n), mais ce n'est qu'une consequence de la compléxité.
Une autre consequence est par exemple de dire qu'un algo en O(n!) est un algo dont la complexité le rend inoperable pour un grand nombre d'elements (20! = 2432902008176640000)

D'ailleurs, si on prend deux algo, le premier parcour un tableau deux fois alors que le second ne le fait qu'une seule fois. Les deux effectueant une seul operation par element. Il est claire que le premier est 2 fois plus lent que le premier, pourtant les deux sont de compléxité O(n).

Comme on peut le voir, la complexite ne pemet pas de differencier tous les algo, sauf cas evidents. Elle permet simplement de prevoir le comportement de l'algorithm dans les cas extremes, c'est d'ailleurs pour cela que la plupart du temps, quand on parle de complexite, on parle réelement de complexité au pire des cas ( d'autres types existent comme la complexité en moyenne...).
Parfois, le pire des cas, n'intervient jamais dans le domaine d'application de l'algo.

Le temps d'execution, lui est un autre critére, qui comme son nom l'indique permet de tester la rapidité de l'algorithm. D'autre critéres existent , telque l'occupation de la mémoire, la frequence d'utilisation...

Ps: comme l'a precisé FR119492, la complexite et le temps d'execution vont generalement de paire, sauf quelques exceptions.

[logo98]

Merci à vous deux.
Pourriez vous me donner les étapes à faire pour calculer la complexité d'un algorithme quelconque.

Merci encore pour vos explications.

[souviron34]

• ecrire l'algorithme
• l'analyser
• additionner

[compdev]

Bonjour,

la complexité des algorithmes est un domaine fortement lié au calcul de la fiabilité et de la "sûreté" de l'algorithme. Les algorithmes à temps d'exécution polynomial (P) sont beaucoup moins complexes que ceux à temps Non polynomial (NP). Beaucoup cherchent à transformer un algo NP en un algo P !!! Ce n'est pas toujours réussi, malheureusement.

Un temps polynomial (P) est proportiionnel à t^a (t puissance a où a est un nombre réel) alors qu'un temps NP est proportionnel à a^t !!! qui croit très très rapidement avec la quantité de l'information à traiter et peut même prendre des milliards et des milliards d'années.

L'exemple de la célèbre tour de Hanoï le montre bien.

Au fait, on ne sait pas toujours si NP=P???? est-ce que tout problème NP est transformable en un problème P????

Bon courage