Version imprimable
Salut,
J'aimerai étudier la complexité d'implémentation d'un algorithme donné dans un problème donné, j'aimerai comprendre la méthode à suivre, comment procéder, je suis un peu perdue et j'aimerai faire une étude éfficace, quels conseils/ docs/liens pouvez vous me recommander?
Merci, vous me serez d'une grande aide!
voir "complexité cyclomatique" ou metrique de Mac CABE qui donne une mesure en fonction du nombre de noeuds et de branches.Citation:
Envoyé par saou88
cordialement
Merci bcp, j'ai cherché un peu à propos de "complexité cyclomatique", c la 1ere fois j'en entends parler, merci pour l'information.Citation:
Envoyé par okaparka
Mais, moi je ne cherche pas à optimiser un code source, plutôt évaluer la complexité d'un algorithme en fonction d'opération de calcul (les multiplications) et je n'ai pas trouvé un doc à l'appui.
Merci!
ça c'est exactement dans le cadre de la complexité cyclomatique http://en.wikipedia.org/wiki/Cyclomatic_complexity, qui compte le nombre d'opérations élementaires..Citation:
Envoyé par saou88
Sinon la complexité "normale" est plutôt la Complexité computationnelle
Merci, oui c'est plutôt ce deuxième lien.Citation:
Envoyé par souviron34
cordialement.
ben disons que c'est peu compatbible avec ton post précédent :
La complexité décrite dans le second line est la générale, qui définit en général l'attitude l'algorithme en fonction de la taille de l'entrée :
Elle est sensible aux chosees comme les boucles. Par contre, les nombres ou types d'opérations dedans sont exclus.
La complexité cyclomatique elle est fonction du nombre d'instructions élémentaires. On peut donc la diviser en fonction des additions, divisions, multiplications etc..
Bonjour,
je pense beaucoup de réponses à tes questions dans le livre d'introduction à l'algorithmique de Cormen et al. C'est la référence dans le domaine. Il existe une traduction française de l'ouvrage chez Dunod je crois.
Ce n'est pas ce que j'ai vu sur Wikipedia par contre. D'après wikipedia (Cyclomatic Complexity), la complexité cyclomatique se base sur le graphe de flot du code source et contrairement à ce que vous dites, c'est elle qui est sensible aux boucles.Citation:
Envoyé par souviron34
Merci bien.
Cordialement.
Merci pour la proposition, mais je ne peux accéder aux ouvrages payants, hélas.Citation:
Envoyé par Aleph69
Tout est dans la définition de la métrique..Citation:
Envoyé par saou88
Dans Context of computational complexity regarde le chapitre "Metric being measured".
Dans Computational complexity theory regarde l'ensemble, en particulier la définition :
Tu as ensuite Analysis of algorithms, qui t'introduira à Big O notationCitation:
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty,
Enfin, dans le lien sur la complexité cyclomatique, tu as un exemple.
Dans cet exemple, tu verras que le if..then..else est catégorisé avec une complexité de 3.
Or de manière pratique ça ne veut rien dire, car on ne connait pas la complexité des fonctions f1 ou f2 appelées..
Si f1 est une inversion de matrice 3D, et que f2 est un tri, il bien évident que ce qui intéressera le lecteur est pas le chiffre 3 mais le chiffre - symbole correspondant à ce que prendra la fonction f1 ou f2.
Maintenant compare cet exemple avec celui donné dans la page dédiée à l'anaylse des algorithmes..
Donc, je me répète, la première des choses à faire est de calculer la complexité en terme de Big O : les limites intrinsqèues par rapport à la taille de l'entrée.Citation:
A given computer will take a discrete amount of time to execute each of the instructions involved with carrying out this algorithm. The specific amount of time to carry out a given instruction will vary depending on which instruction is being executed and which computer is executing it, but on a conventional computer, this amount will be deterministic
Ensuite, et ensuite seulement, tu peux raffiner/améliorer/optimiser la vraie complexité "cyclomatique" au sens du nombre de cycles nécessaires en par exemple remplaçant les divisons par des multiplications (qui prennent moins de temps), ou...
Danc ce dernier sens, par exemple, on peut optimiser un appel à des éléments successifs dans un tableau en diminuant le nombre d'opérations élémentaires pour les atteindre : au lieu de faire tab|i], qui va demander une addition plus une multiplication (zéro + taille*i), tu peux optimiser en utilisant un pointeur, et tu n'auras plus qu'une addition pour changer d'élément.
Mais ce genre d'optimisation peut être mentionnée, mais ne modifie pas la qualité intrinsèque de limitation de taille due aux boucles..
Si je fais :
ce sera exactement la même complexité limitative que si je faisCode:
2
3
4
5
6
même si j'ai plus d'instructions élémentaires dans le second cas, la complexité de l'algo sera toujours en O(NM).Code:
2
3
Le premier sera plus efficace, mais la complexité du tout sera exactement la même : si je multiplie M par 10, le temps mis sera proportionnel à ce nouveau M...
La complexité non cyclomatique donne au lecteur l'information de proportionnalité, ce qu'il peut attendre de l'algo en fonction de son entrée :
- dans un algo linéaire, si on double la taille de l'entrée, on double le temps (running time) (quel qu'il soit, avec ou pas moins d'opérations élémentaires)
- dans un algo quadratique, si on double la taille de l'entrée on multiplie par 4 le temps..
- ...
C'est pour ça que c'est la manière de mesurer la complexité la plus courante : ça donne de l'information pas sur une implémentation, mais sur l'algorithme en lui-même, le principe... Et donc ça donne une information prédictive sur le comportement, quelle que soit la machine...
ça donne une information relative : si je double le nombre entré, ça prendra X fois plus de temps..
Oui c'est exactement ce que je veux savoir. je ne sais pas comment vous remercier pour toutes ces explications et pour votre temps. 1000*MERCI!!!Citation:
Envoyé par souviron34
FYI http://www.quora.com/Mathematical-Pr...m-complexitiesCitation:
Envoyé par saou88