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

[Tuxico]

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.

Je suis d'accord mais, le calcul de complexité permets d'avoir une idée générale de l'efficacité d'un algo. sur toute machine, quelle que soit son matériel. Si tu as besoin d'un temps sur une machine en particulier, alors oui, c'est complètement différent et ça dépends notamment des bus/caches de ta RAM etc. Mais cette méthode permets souvent d'éviter des algos exponentiels qui ont l'air de tourner bien sur des petits échantillons de données, donc on est content, tout va bien, mais une fois que tu passes par des gros échantillons de données, il se peut que tu en ais pour 10 ans pour calculer une bête série par exemple.

@++

[FR119492]

Salut !

il se peut que tu en ais pour 10 ans

Là, tu es encore optimiste. Un de mes amis avait calculé que, pour un système linéaire de 100 équations à 100 inconnues, sur un Cray I, par la méthode de Cramer, si on avait commencé au moment du big bang qui a donné naissance à notre univers, ça ne serait pas encore fini, alors que la bonne vieille méthode de Gauss ne nécessiterait qu'environ 1 seconde.

Mais que la vie serait belle si certains profs cessaient d'enseigner des méthodes inutilisables.

Jean-Marc Blanc

[HanLee]

Salut !



Là, tu es encore optimiste. Un de mes amis avait calculé que, pour un système linéaire de 100 équations à 100 inconnues, sur un Cray I, par la méthode de Cramer, si on avait commencé au moment du big bang qui a donné naissance à notre univers, ça ne serait pas encore fini, alors que la bonne vieille méthode de Gauss ne nécessiterait qu'environ 1 seconde.

Mais que la vie serait belle si certains profs cessaient d'enseigner des méthodes inutilisables.

Jean-Marc Blanc

Je ne crois pas qu'un prof ait déjà conseillé d'utiliser du Cramer pour du calcul scientifique...

On montre Cramer pour montrer que ça existe, pour des démos, etc. mais pas pour la pratique!

[benDelphic]

une complexité d'un algorithme est le rapport du nombre d'opérations élémentaires et la taille des données.
pour mieux comprendre il faut d'abord commencer par un cours sur la dominance de deux fonctions . une fonction f est dite o(g) ou bien négligeable devant g si il existe k non négatif, il existe L a partir du quel quel que soit x supérieur à L
f(x) est inférieure à k g(x) à un signe prés.Cette notation s'appelle Notation de Landau
voila en résumé sinon il y a beaucoup de cours sur le cher Google

[FR119492]

Salut HanLee!

Je ne crois pas qu'un prof ait déjà conseillé d'utiliser du Cramer pour du calcul scientifique...

En rôdant l'autre jour chez un libraire, je suis tombé par hasard sur ce chef-d'oeuvre:

R. Zouhhad, J.-L. Viviani, F. Bouffard: "Mathématiques Appliquées, Manuel et Applications", Dunod.

Bonne lecture.
Jean-Marc Blanc

[O( N )]

Simplement la complexité sert à déterminer le temps de réponse
et l'espace mémoire utilisé par ton programme.

Pour le calculer tu dois apprendre quelques cours de mathématiques
de niveau bac à bac + 2 environ.
(série, suite entre autres joyeusetés.)

Les algorithmes sont rangés en classes de problèmes afin de mieux savoir
combien de temps il te faut pour répondre à certains problèmes connus.

Pour le calcul une méthode générale + des maths voilà et biensûr tu les verras
dans les cours proposés plus haut !

Bonne lecture

[alex_pi]

Je tiens à préciser que "la complexité" d'un algorithme ne veut en général rien dire. On doit souvent distinguer la complexité moyenne, la complexité dans le pire des cas, la complexité amortie, et que suivant les cas, certains algo peuvent passer du statut de "mauvais" à "très bon"... Par exemple, le quicksort a une complexité quadratique (en n^2) dans le pire des cas, ce qui le rend bien oins bon qu'un tri fusion qui a toujours une complexité en n log(n), mais il a en fait une complexité moyenne en n log(n) et une meilleure constante qui le rend plus efficace.
Certaine structure de donnée peuvent avoir des temps d'accès catastrophique dans le pire des cas (un accès prenant un temps très long), mais avoir une complexité amortie excellente (si un accès prend un temps très long, pendant un certain temps, tous les accès seront nécessairement rapide par exemple).
La complexité n'est pas un domaine trivial :-)

Bonne chance