le terme "computational complexity"

[souviron34]

oui, mais je crois que Aleph t'as un peu emmêlé les pinceaux..

(et d'ailleurs il le mentionne :

en posant H(x)=log(G(N)), a=k, b=log(ck) et X=log(N).

)

là, ce que tu prouves, c'est que le log de ta fonction est proportionnel à N, donc que ta fonction est proportionnelle à l'exponentielle de N

Si tu traces f(x) vs x, si tu mets une échelle log en X : (une échelle, hein ??)

• si tu as une droite : ta fonction est bien en log(N)
• si tu mets une échelle log en Y (tout en gardant l'echelle log en X), et si tu as une droite, alors c'est une loi de puissance, dont le coefficient de pente te donnera la puissance..

PS: ta légende est fausse, puisque tu n'as pas une échelle log en x..

[Décembre]

Salut,

Envoyé par souviron34

oui, mais je crois que Aleph t'as un peu emmêlé les pinceaux..

(et d'ailleurs il le mentionne :

)

là, ce que tu prouves, c'est que le log de ta fonction est proportionnel à N, donc que ta fonction est proportionnelle à l'exponentielle de N

Si tu traces f(x) vs x, si tu mets une échelle log en X : (une échelle, hein ??)

• si tu as une droite : ta fonction est bien en log(N)
• si tu mets une échelle log en Y (tout en gardant l'echelle log en X), et si tu as une droite, alors c'est une loi de puissance, dont le coefficient de pente te donnera la puissance..

comment dois-je faire pour l'échelle? je suis perdue

[Aleph69]

Bonjour,

Envoyé par Aleph69

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.

Mea culpa! Une erreur s'est glissée ici : il faut tracer log(T) en fonction de log(N) bien sûr!

Tu ne dois avoir qu'un seul et unique graphique : celui de log(T) en fonction de log(N). Si tu obtiens une droite pour N grand, alors la complexité de ton algorithme est polynomiale. Sinon, il faut chercher ta loi sous une autre forme.

Merci souviron34!

[Décembre]

Envoyé par Aleph69

Bonjour,



Mea culpa! Une erreur s'est glissée ici : il faut tracer log(T) en fonction de log(N) bien sûr!

Tu ne dois avoir qu'un seul et unique graphique : celui de log(T) en fonction de log(N). Si tu obtiens une droite pour N grand, alors la complexité de ton algorithme est polynomiale. Sinon, il faut chercher ta loi sous une autre forme.

Merci souviron34!

Regardez ce que j'ai obtenu en traçant:

- Log(t) en fonction de log(n)-->O(n)
- Log(t) en fonction de log(n²)-->O(n²)
- Log(t) en fonction de log(n^3)-->O(n^3)
- Log(t) en fonction de log(log(n))-->O(log(n))
- Log(t) en fonction de log(n*log(n))-->O(n*log(n))

Il n 'ya que des lignes droites...que choisir maintenant

[souviron34]

je ne sais pas ce que tu fais.. Tu n'as pas 2 fois la même échelle pour X : 10, 32, .. 4..

Reprenons...

De quel outil te sers-tu pour tracer ?? Avec gnuplot, il suffit de faire "set logscale x".

[Décembre]

Salut,

Je trace avec matlab et les valeurs que je trace sont sur le poste #22 sous forme d'un fichier excel

[Aleph69]

Décembre, c'est pourtant clair :

Envoyé par Aleph69

Tu ne dois avoir qu'un seul et unique graphique : celui de log(T) en fonction de log(N).

[souviron34]

je ne peux l'ouvrir avec mon Excel...

Mais maintenant, je ne connais pas Matlab, mais je suis certain qu'il y a, sns calculer quoi que ce soit, juste le moyen de modifier les échelles du tracé..

[Décembre]

je ne peux l'ouvrir avec mon Excel...

Je pense que c'est un problème d'extension essayez celui la:

[souviron34]

si j'en crois ton premier graphique précédent, si il est bien ce qui correspond à ce que Aleph69 a dit (log(f(N)) <-> log(N)), alors :

pour un delta de 1.85 en log(N) (entre 10.7 quand ça touche en haut et 8.85 quand ça touche en bas) , tu as un delta de 4 en log(f(N)). A vue de nez, comme ça, juste en regardant.

C'est donc légèrement supérieur à O(N^2)... (O(N^2.16)) (puisqu'alors pour un delta de 2 en logN tu aurais 4 en log((n)))

Pour avoir le vrai coeff, il te faut faire une régression linéaire sur ce graphique.

[Décembre]

si j'en crois ton premier graphique précédent, si il est bien ce qui correspond à ce que Aleph69 a dit (log(f(N)) <-> log(N)),

Le graphique de quel poste s'il vous plait?

[souviron34]

numéro 24, juste au dessus..

[pseudocode]

Envoyé par Décembre

Je pense que c'est un problème d'extension essayez celui la:

D'après les données de ton fichier excel, on voit bien que ta fonction "t(n)" domine n.log(n) mais est dominée par n^3.

Et comme la courbe pour n^2 semble assez linéaire, on suspecte fortement que t(n) se comporte comme a*n^2.

[Décembre]

Envoyé par pseudocode

D'après les données de ton fichier excel, on voit bien que ta fonction "t(n)" domine n.log(n) mais est dominée par n^3.

Et comme la courbe pour n^2 semble assez linéaire, on suspecte fortement que t(n) se comporte comme a*n^2.

Merci beaucoup pour l'explication, donc il se comporte comme un a*n^2, pour le coefficient a (la pente). est ce que c'est juste de le calculer graphiquement à partir de mes données? car mon programme et très complexe et fait appel à plusieurs fonctions et c'est pas très simple de calculer la complexité directement !!

Merci encore