Compléxité?

Signaler
Messages postés
30
Date d'inscription
mercredi 12 avril 2006
Statut
Membre
Dernière intervention
17 avril 2007
-
Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
-
Bonjour à tous;
Est ce que c'est possible de savoir la compléxité de mon algorithme ou code C++?? nombre d'opérations ou temps de calcul??
Bonne journée.
Merci à tous
Najia

4 réponses

Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
avec une différence de résultats de time(), tu peux calculer le temps d'exécution. Mais ce n'est pas très précis.
Une complexité théorique se calcule à la main

_____________________________________
Un éditeur de ressources gratuit pour Windows
Messages postés
30
Date d'inscription
mercredi 12 avril 2006
Statut
Membre
Dernière intervention
17 avril 2007

Merci;
Sinon, comment appliquer la fnction time()??
Merci à tous
Najia
Messages postés
6535
Date d'inscription
lundi 16 décembre 2002
Statut
Modérateur
Dernière intervention
22 août 2010
7
time_t t1 = time(NULL);
...
int temps = time(NULL) - t1;
_____________________________________
Un éditeur de ressources gratuit pour Windows
Messages postés
1329
Date d'inscription
vendredi 15 août 2003
Statut
Membre
Dernière intervention
16 juin 2010
2
( tiens Vecchio t'es admin maintenant ? :)  )
ffnajia -> ça dépend de c que tu veux savoir.
Tu peux calculer la complexité algoritmique de ton algo, genre si dedans t'as un for ( 0 -> n), la complexité sera notée 0 (n) ... si t'as un arbre binaire en général ce sera O ( ln (n) ).
Ca te renseigne sur la capacité de ton algo a gérer un grand nombre de données, en gros.

Si c'est du temps que tu veux : QueryPrecisionTimer ou un truc dans le genre , RTFM ( aka MSDN ^^ ), mais il doit y avoir plus portable.
Evite à tout prix time() ou autres, précision lamentable ... sauf bien sûr si ton algo dure plus d'une seconde, dans ce cas c'est pas bien méchant

3ème option, ou va ma préférence : RDTSC, une instruction assembleur qui retourne le nombre de ticks depuis le dernier reboot. En gros ça te donne le nombre d'instructions qu'il a fallu pour arriver d'un point à un autre de ton prog, pour le coût d'une simple division et de 2 opcodes asm. Attention ce combre est indépendant du PC sur lequel tu l'utilises ( à peu pres ), mais pas du nombre de processus en cours ( si t'as half-life qui tourne en même temps, ça va consommer 95% du CPU et donc multiplier ta valeur par ... beaucoup ^^ ) goto Wikipedia pour plus de détails ...

++
ad

_______________________

Omnia vincit labor improbus