Discussion :

[space_56]

bonjour,
dans un algorithme, que signifie la complexité ?
et comment la trouve-t-on ?
merci.

[souviron34]

une petite recherche sur ce site t'aurait amené ici, juste la page suivante....

[Invité]

Bonjour,
pour résumé la complexité est le nombre de boucle imbriqué.
Ex :

pour (i allant de 1 à n) { code

pour (j allant de 1 à m) {

code

}

code }

--> complexité O(n*m)

par contre si tu as

pour i allant de 1 à n {code}

pour j allant de 1 à m {code}

--> complexité O(Max(n,m))

Après suivant la complexité de ton algorithme et l'optimisation que tu vas faire afin de réduire le temps de calcul, tu tombes sur une fontion mathématique du style log, exp.
Bonne journée

[contremaitre]

Bonjour,
pour résumé la complexité est le nombre de boucle imbriqué.

tu oublies la complexité de "code"

[millie]

Jette un oeil au cours : http://lapoire.developpez.com/algorithmique/initiation/ à partir de la page 33

[FR119492]

Salut !

Attention!
Le temps de calcul est souvent très loin d'une quelconque fonction simple de la complexité. Deux exemples:

• En se basant sur la notion de complexité, on pourrait penser que le temps de calcul pour résoudre un système linéaire est en n^3, donc représentable par une cubique. Si tu essaies, ce que j'ai fait (sous Windows), tu constateras une discontinuité au moment ou ça commence à "swapper" sur disque.
• Pour le même problème, j'ai écrit une fois une routine la plus simple possible (en Fortran) et j'ai comparé le temps de calcul avec celui obtenu avec la routine DGECO de la librairie LinPack. Celle-ci m'a donné des temps de calcul significativement plus courts.

Conclusion:
La complexité peut être utile pour éliminer des algorithmes certainement mauvais (comme la méthode de Cramer), mais elle ne dispense pas de comprendre comment un ordinateur calcule, si on veut vraiment optimiser un programme.

Jean-Marc Blanc