le terme "computational complexity"

[Décembre]

Bonsoir,

J'ai écrit un programme qui traite un maillage 3D, sur ma machine j'ai effectuer quelques tests avec différents maillages 3D (je changeais à chaque fois le nombre de cellule du maillage) et j'ai noté à chaque fois le temps d’exécution ce qui m'a permis de tracer la figure ci-jointe avec Excel.

J'ai vu sur certain document le terme "computational complexity" et mes recherche m'ont aidées à comprendre que ce terme ne veut pas dire temps d’exécution, pouvez vous m'éclairer s'il vous plait?

merci

[souviron34]

De manière générale c'est la définition du comportement de l'algo en foncton de la taille de l'entrée..

Elle est souvent calculée - et est représentative - comme le "noeud", c'est à dire la plus grosse partie de l'algo..

Par exemple une boucle simple sur N éléments sera dite O'N). Une double boucle sur N et M éléments (une matrice) sera O(N*M). On néglige les facteurs constants : quand on dit "un algo est en O(N^2), on dit que c'est "proportionnel au carré de l'entrée"..

Il faut donc analyser chaque partie de ton algo et en tirer la partie donnant la plus grosse dépendance : c'est ce qui limitera..

Bien entendu, il peut y avoir plusieurs types de complexités. Regarde Wiki..

La plus courante est celle que j'ai indiquée...

[Aleph69]

Bonjour,

la complexité (temporelle) d'un algorithme correspond au nombre d'opérations effectuées en fonction des données. Il s'agit donc d'une mesure de performance comme l'est le temps d'exécution. La différence essentielle entre les deux notions est que le temps d'exécution d'un algorithme pourra varier selon l'architecture : les calculateurs sont de plus en plus performants et les temps d'exécution tendent à diminuer. Ce n'est pas le cas de la complexité qui, en ce sens, est une meilleure mesure de performance que le temps d'exécution.

[Décembre]

Salut et merci pour vos réponses

Grace à vous j'ai trouver un document qui parle de "comutational complexity" mais il cite différents ordres:

O(1) constant
O(loga n) logarithmic
O(n) linear
O(n loga n) \n log n"
O(n2) quadratic
O(n3) cubic
O(nr) polynomial
O(an) exponential
O(n!) factorial

Comment peut-on savoir quel cas de figure est le notre (je parle de la liste d'ordre ci-dessus)

merci

[pseudocode]

Envoyé par Décembre

Comment peut-on savoir quel cas de figure est le notre (je parle de la liste d'ordre ci-dessus)

Puisque tu as les valeurs mesurées pour ton algo, le plus simple c'est de tracer la courbe suivant chaque échelle (n, n^2, log(n), ...) et regarder laquelle donne une ligne droite.

[Décembre]

Salut,

Puisque tu as les valeurs mesurées pour ton algo, le plus simple c'est de tracer la courbe suivant chaque échelle (n, n^2, log(n), ...) et regarder laquelle donne une ligne droite.

C-à-d je prends les valeurs (que j'ai mise sur l'axe des x) sur la figure que j'ai joint à mon premier message et j'essaie de trouver laquelle se rapproche le plus d'elle?

[pseudocode]

Envoyé par Décembre

C-à-d je prends les valeurs (que j'ai mise sur l'axe des x) sur la figure que j'ai joint à mon premier message et j'essaie de trouver laquelle se rapproche le plus d'elle?

Chaque point de mesure Pi a pour coordonnées un couple de valeur (Xi,Yi).

Il te suffit de tracer les nuages de points suivants:
* nuage des points (Xi,Yi)
* nuage des points (log(Xi),Yi)
* nuage des points (Xi^2,Yi)
...

Le nuage de point qui forme une ligne t'indiquera le type de complexité.

[Décembre]

Le nuage de point qui forme une ligne t'indiquera le type de complexité

Excusez mon ignorance, mais pourquoi devrais-je chercher une ligne?

merci

[souviron34]

parce que avec une corrélation linéaire tu as un coefficient de corrélation... Ce qui n'est pas directement atteignable avec des fits divers ou variés : tout ce que tu pourras avoir c'est des écarts relatifs, et tu pourrais mentionner le max..

Dans le cas d'un fit linéaire, le coefficient de corrélation est une mesure reconnue par tout le monde : un coefficient de confiance..

Si c'est linéaire, y'a pas de problèmes.
Si c'est expoentiel, ça devient plus compliqué.. Une superposition de courbe ferait illusion, mais ne donnerait pas d'indications précises.

Donc, si ton algo se comporte en O(N^2), si tu prends le log, tu devrais avoir une droite de pente 2.

[pseudocode]

Envoyé par Décembre

Excusez mon ignorance, mais pourquoi devrais-je chercher une ligne?

Souviron34 à très bien expliqué la raison.

Pour faire simple, si tu as une complexité en N^2 alors les points Pi forment visuellement une parabole. Pi = (Xi,Yi) ~= (Xi, a.Xi^2)

Comme visuellement c'est dur de reconnaitre une parabole, il est plus pratique de changer l'échelle sur l'axe X --> Qi = (Xi^2,Yi) ~= (Xi^2, a.Xi^2)

Dans ce cas, les points Qi forment visuellement une droite. C'est plus facile a reconnaitre.

[Décembre]

Salut et merci pour votre aide

Comme vous pouvez le constater sur la figure jointe, je n'ai pas obtenu de ligne droite en traçant les différente fonction

Que dois-je faire d'après vous ?

merci

[souviron34]

Envoyé par Décembre

Que dois-je faire d'après vous ?

D'une part avoir plus de points de mesure...

Là, d'après ce qu'on peut voir, ça semblerait en O(N^2)...

Ce qui serait pas mal pour un maillage 3D, et normal pour un 2D.

Ensuite, analyser plus propement ton algorithme, comme je l'ai expliqué dans la discussion Etude de complexité de l'implémentation d'un algorithme donné, en particulier au post #10

[Décembre]

Bonsoir et merci de m'avoir répondue

Code :

1
2
3

Là, d'après ce qu'on peut voir, ça semblerait en O(N^2)...

ça ne ressemblerai pas à un O(nlog(n))?
merci d'avance

[souviron34]

Envoyé par Décembre

ça ne ressemblerai pas à un O(nlog(n))?

Avec aussi peu de points difficile à dire, mais ça n'a pas l'air.. : ça a l'air de démarrer plat puis de monter..

Alors que la courbe en N^2 a l'air plus droite..

[Aleph69]

Bonsoir Décembre,

peux-tu nous donner les grandes étapes de ton algorithme?

[Aleph69]

Envoyé par Décembre

ça ne ressemblerai pas à un O(nlog(n))?

Bien que je ne cautionne pas l'approche adoptée, je pense que tu auras une meilleure idée du comportement de ton algorithme en ayant plus de points de mesure. Idéalement, il faudrait une trentaine de points de mesure à égale distance les uns des autres en abscisse (grossièrement bien sûr) et pour des grandes valeurs de n (ce que tu fais déjà) puisqu'on souhaite uniquement une tendance asymptotique. Il se peut que, pour une raison à déterminer, tu sois en présence de valeurs aberrantes bruitant trop fortement ton problème de régression (à cause du faible nombre de points).

EDIT : conserve les points de mesure dans une table que tu pourras poster afin que chacun puisse t'aider à trouver l'équation mystère...

[Décembre]

Bonsoir,

J'ai pris plus de valeur comme vous me l'aviez recommandé et vous avez raison la ligne droite se confirme pour le O(n²).

J'ai lu certain document mais j'avoue que je n'arrive toujours pas à comprendre comment et pourquoi on obtient une ligne droite à la complexité temporelle de l'algorithme?

[Aleph69]

Bonsoir,

Envoyé par Décembre

J'ai lu certain document mais j'avoue que je n'arrive toujours pas à comprendre comment et pourquoi on obtient une ligne droite à la complexité temporelle de l'algorithme?

C'est très simple. Ce que tu cherches est la loi F liant le temps d'exécution T à la taille N des données :

T=F(N)

Tu es face à un problème de régression. L'idée la plus naturelle consiste à chercher F sous la forme d'un polynôme d'un certain degré k (inconnu) :

F(N)=c0+c1*N+c2*N²+...+ck*N^k,

où c0,...,ck sont des coefficients réels (inconnus).
Lorsque que N grandit (tend vers l'infini), le terme de plus haut degré, c'est-à-dire ck*N^k, grandit plus vite que les autres termes et finit par devenir tellement grand par rapport aux autres que les valeurs de F(N) et ck*N^k sont presque les mêmes. En d'autres termes, la somme

F(N)-ck*N^k = c0+c1*N+c2*N²+...+c_{k-1}*N^{k-1}

joue un rôle mineur dans l'évaluation de F(N). Mathématiquement, il suffit de diviser F(N) par ck*N^k pour le voir, puisque le membre de droite dans

F(N)/(ck*N^k) = c0/N^k + c1/N^{k-1}+...+c_{k-1}/N+1

tend vers 1 quand N tend vers l'infini. Pour signifier cela de façon synthétique, on utilise la notation de Landau

F(N)=O(N^k)

Bref, en prenant N suffisamment grand, on peut identifier F(N) à la fonction G(N)=ck*N^k en commettant une erreur d'approximation très petite. Le problème ici est maintenant d'identifier le degré k (et éventuellement le coefficient ck). Visuellement, il est très difficile de différencier des puissance entre elles comme tu as pu le constater. Pour faciliter cette étape, et dans le cas particulier d'une puissance, on regarde plutôt le logarithme car

log(G(N))=log(ck*N^k)=log(ck)+log(N^k)=log(ck)+k*log(N)

est l'équation d'une droite que l'on peut écrire plus simplement sous la forme

H(x)=a*x+b

en posant H(x)=log(G(N)), a=k, b=log(ck) et X=log(N). Concrètement, il te suffit donc de faire des mesures (N,T) pour N assez grand, puis de tracer, non pas T en fonction de N, mais log(T) en fonction N. Si la relation entre N et T est polynomiale, alors tu obtiendras (aux erreurs de mesure près) une droite de coefficient directeur le degré k de ton polynôme et d'ordonnée à l'origine le logarithme log(ck) du coefficient ck associé au terme prépondérant N^k. Hormis une analyse sur papier de ton algorithme pour déterminer exactement sa complexité (même pour N petit), la meilleure façon d'estimer la pente a et l'ordonnée à l'origine b de ta droite est la méthode statistique appelée régression linéaire.

J'espère que tout est clair.

Pense bien à passer ce sujet en résolu et bon courage pour la suite.

[Décembre]

Merci Aleph69 ton explication est vraiment très très claire

merci encore pour vous tous

[Décembre]

puis de tracer, non pas T en fonction de N, mais log(T) en fonction N.

ça change tout !! regardez l'image jointe avec log(t) en fonction des n la complexité à l'air d'être log(n)