Discussion :

[_kal_]

Bonjour,

J'ai une fonction de complexité n*log2(n) avec log2 = log base 2. Je cherche une relation liant cette complexité en fonction de n au temps d'execution moyen sur un processeur d'environ 2GHz.

En l'occurence, ici, mon n vaut 5*10^5.

Merci d'avance

[borisd]

Je ne suis pas spécialiste, mais je dirais que ça dépend beaucoup :
- du matériel : la fréquence du processeur seule est loin de caractériser la vitesse d'exécution globale du programme
- de la complexité moyenne de l'algorithme. Si O(n*log2(n)) est la complexité au pire, cela peut ne pas refléter du tout la complexité moyenne
- du tas de constantes qui se cachent derrière O(n*log2(n))
Peut-être qu'il serait judicieux (je ne l'ai jamais fait, je ne sais pas trop) d'effectuer une série de tests sur des jeux de données de tailles différentes puis d'effectuer une sorte de régression ou autre pour estimer les paramètres d'un modèle du type T(n)=(n+k1)*log2(n+k2)+k3.

[Edit] Attention aussi aux autres termes occultés dans O(n*log2(n)), comme par exemple un traitement qui s'effectue en O(n), mais qui peut avoir son importance selon la taille des instances.

[gangsoleil]

Bonjour,

Bonjour,

J'ai une fonction de complexité n*log2(n) avec log2 = log base 2. Je cherche une relation liant cette complexité en fonction de n au temps d'execution moyen sur un processeur d'environ 2GHz.

En l'occurence, ici, mon n vaut 5*10^5.

Merci d'avance

32 secondes ?

Pour être plus sérieux, ca dépend de plein d'autres composants que le processeur, mais aussi de la taille des données manipulées, et surtout de la manipulation effectuée avec ces données : si tu travailles sur un grand nombre de donnée, mais que pendant de relativement grands laps de temps tu travailles sur les mêmes données, alors si celles-ci tiennent dans le cache processeur, alors tu vas gagner du temps.
En revanche, sur des algorithmes de tri où tu passes ton temps à comparer différentes valeurs, celles-ci doivent continuellement être copiées de la mémoire dans le cache avant de pouvoir effectuer la comparaison, ce qui prend plus de temps que de faire un calcul...

Bref, tu n'auras jamais de réponse, et ce d'autant plus que les OS d'aujourd'hui sont tous multi-tâches, et donc tu pourras au mieux avoir une approximation de la moyenne que tu as pu calculer pour une charge CPU donnée, avec une certaine versionde patch de l'OS chargée, ...

[jobherzt]

Un truc que tu peux essayer, a tout hasard :

si c'est en O(machin), ca veut dire qu'il existe une constante k telle que le temps d'execution soit en gros k*machin.


Donc tu peux lancer ton programme avec des petites valeurs de n, plein de fois, tu notes le temps moyen pour chaque valeur de n et tu fait une regression lineaire pour trouver k. ca ne sera pas juste au micropoil, mais ca te donnera un ordre de grandeur !

[borisd]

Un truc que tu peux essayer, a tout hasard :

si c'est en O(machin), ca veut dire qu'il existe une constante k telle que le temps d'execution soit en gros k*machin.


Donc tu peux lancer ton programme avec des petites valeurs de n, plein de fois, tu notes le temps moyen pour chaque valeur de n et tu fait une regression lineaire pour trouver k. ca ne sera pas juste au micropoil, mais ca te donnera un ordre de grandeur !

C'est à peu près ce que j'ai proposé plus haut
Par contre, je pense que l'échantillon doit contenir des jeux de données de tailles assez différentes les unes des autres pour pouvoir extrapoler le comportement la fonction.

[Sivrît]

Cela dit les O(bidule) sont des comportements asymptotiques qui donnent une équivalence (et non une égalité) pour quand la taille devient substancielle, pas une formule pour trouver "54ms avec n=3". Donc mieux vaut des jeux de données passablement grands et ajouter des constantes et... enfin comme borisd quoi.

[HanLee]

Heu, grand O c'est qu'une majoration, c'est pas un thêta !

Quelque chose de la forme O(n) implique qu'il est de la forme O(n * log(n)), et aussi O(n²).

Donc c'est pas équivalent à n multiplié par une constante.

La bonne notation c'est thêta, pour l'équivalence (f = theta(g) <=> f = O(g) et g = O(f)).

[Sivrît]

Après un brin de révisions (http://fr.wikipedia.org/wiki/Notations_de_Landau)... oopsy , j'ai tout mélangé dans ma tête.

Ben un grand O ça ne dit pas grand chose en définitive. Au final, on essaie pour différentes tailles, on trace un graphe et on utilise notre bonne vieille capacité à s'exclamer "tiens, ça resemblerait pas à un log ça ?"

[nletteron]

La réponse est simple, il n'existe aucune formule liant le temps d'exécution à la complexité.



Même au niveau matériel deux processeurs de 2 GHz sont potentiellement différents dans leur mode d'exécution des fonctions basiques. Rien ne prouve qu'effectuer une opération d'ajout du chiffre 1 se fait à 1,3 nanosecondes sur un Pentium et 1,2 nanosecondes sur un AMD.