Bonjour
Lors de la comparaison de deux algorithmes en matière de complexité, est ce qu'on peut se contenter de comparer leurs temps d'exécution?
En d'autres termes, est ce qu'on peut dire qu'on a comparé la complexité en comparant le temps d'exécution?
PS: ma question est par rapport à la complexité en temps (pas celle en espace)
D'avance merci!
"Les méthodes sont les habitudes de l'esprit et les économies de la mémoire"
Bonjour
à mon avis, non un temps de calcul n'est pas tout à fait révélateur de la complexité, et réciproquement.
La complexité est souvent asymptotique, le temps de calcul est par définition ponctuel.
Dans la complexité, il y a souvent un manque d'information sur les constantes multiplicatives : par exemple, pour O(n^4), il se peut très bien que la complexité réelle soit 0.0001 * n^4 , si bien que, pour n pas grand, ce sera inférieure à une complexité 1000 * n^2 (que l'on écrira pourtant O(n^2) ).
Non, en général étudier la complexité d'un algorithme c'est de donner une borne supérieure (souvent sous forme de O() ) du nombre d'opération élémentaires en fonction de la taille des données du problème. Comme dis ci-dessus, si tu compares juste les temps d'execution tu compares pour une instance seulement...
De plus on parle en général de complexité au pire cas et c'est rarement celle que tu rencontre. De ce fait l'algo du simplexe est censé être exponentiel et pourtant il se comporte comme un algo polynomial (la smoothed complexity a apporté une réponse à ce sujet).
Bonjour
Informatiquement ?Envoyé par PrRou_
Merci.
on peut s'attendre à une multi-comparaisons avec une distribution normale des paramètres.
Le premier problème vient de la base de comptage de la complexité. Le processeur de test pourrait privilégier certaines instructions ( c'est toujours le cas ) et utiliser des technologies propres plus ou moins performantes ( optimisation , parallélisme , etc ). Ca n'en fait pas un instrument de mesure très portable. Il suffit de petites révolutions pour que des benchmarks d'algorithmes changent.
quand on ne sait pas, il faut demander
Non je ne pense pas.
Le temps d'exécution n'est pas révélateur de la complexité de ton algorithme.
Car tu ne sais pas le nombre d'opération effectuée.
Il faut borner ton algorithme par une fonction: logarithme, linéaire, quadratique (), cubique, puissance de n, exponentielle etc... lorsque n le nombre d'opérations tend vers l'infini.
Car tu peux très bien avoir un algo en O(n²) plus rapide qu'un algo linéaire, avec peu d'opérations.
