Etude de complexité de l'implémentation d'un algorithme donné

**saou88** · 17/10/2012, 19h55

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!

**okaparka** · 18/10/2012, 03h13

Envoyé par saou88

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.
cordialement

**saou88** · 18/10/2012, 08h03

Envoyé par okaparka

voir "complexité cyclomatique" ou metrique de Mac CABE qui donne une mesure en fonction du nombre de noeuds et de branches.
cordialement

Merci bcp, j'ai cherché un peu à propos de "complexité cyclomatique", c la 1ere fois j'en entends parler, merci pour l'information.
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!

**souviron34** · 18/10/2012, 13h53

Envoyé par saou88

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..

Sinon la complexité "normale" est plutôt la Complexité computationnelle

**saou88** · 18/10/2012, 15h00

Envoyé par souviron34

Sinon la complexité "normale" est plutôt la Complexité computationnelle

Merci, oui c'est plutôt ce deuxième lien.
cordialement.

**souviron34** · 18/10/2012, 15h52

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..

**Aleph69** · 18/10/2012, 17h02

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.

**saou88** · 18/10/2012, 22h27

Envoyé par souviron34

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..

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.

Merci bien.
Cordialement.

**saou88** · 18/10/2012, 22h34

Envoyé par Aleph69

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.

Merci pour la proposition, mais je ne peux accéder aux ouvrages payants, hélas.

**souviron34** · 19/10/2012, 00h56

Envoyé par saou88

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.

Tout est dans la définition de la métrique..

Dans Context of computational complexity regarde le chapitre "Metric being measured".

Dans Computational complexity theory regarde l'ensemble, en particulier la définition :

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,

Tu as ensuite Analysis of algorithms, qui t'introduira à Big O notation

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..

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

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.

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 :

Code :

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

1
2
3
4
5
6
 
Cste = 4*(42^2)
 
for i = 0 ; i < N ; i++ )
   for ( j = 0 : j < M ; j++ )
         tab[i][j] = tab[i][j] + Cste

ce sera exactement la même complexité limitative que si je fais

Code :

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

1
2
3
 for i = 0 ; i < N ; i++ )
   for ( j = 0 : j < M ; j++ )
         tab[i][j] = tab[i][j] + 4*(42^2)

même si j'ai plus d'instructions élémentaires dans le second cas, la complexité de l'algo sera toujours en O(NM).

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..

**saou88** · 19/10/2012, 07h40

Envoyé par souviron34

Tout est dans la définition de la métrique..

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!!!