en fait je me demandais si il existait des logiciels permettant de determiner la complexité d'un algorithme.Si oui,quel serait leur algorithme.
si non,pourquoi ça n'a pas encore était fait?
P.S:oui je sais il est tard
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Discussion :
complexité d'un algorithme par un...algorithme??
en fait je me demandais si il existait des logiciels permettant de determiner la complexité d'un algorithme.Si oui,quel serait leur algorithme.
si non,pourquoi ça n'a pas encore était fait?
P.S:oui je sais il est tard
le mesure de la complexité est en soi un algo
on pourrait la représenter approximativemnent ainsi
(taille du programme)/(taille des données)
tu vois que c'est facile
c'est facile à la main,mais à implementer je crois que c'est une autre paire de manches.Envoyé par random
en effet,on determine toujours la complexité au pire cas(c'est à dire qu'on fait tourner l'algo un nombre maximum de fois)
je ne vois pas du tout comment faire un algo de la sorte
ben en fait c'est complexe de mesurer la complexité d'un algo !
dabord il y a un point important : est-ce qu'il fonctionne et si oui avec ou sans bug de cas particuliers genre : x/0 = impossible
ensuite comme l'a dit random ya la taille des donnée puis le fait que tu duplique ou non tes donées (néssésité de l'algorithme) enfin il y a aussi le raport poid de code / vitesse d'execution * fiabilité ect....
bref voila pourquoi c'est peut etre pas encore développé !
sinon tu peux essayer de faire des recherches dans le dommaine des algorithmes cognitifs a base genetique (on teste 1000 procedure, on garde que les 10 + efficaces, on crée 100 variantes de chaques on les testent ect...)
Tout à fait, il faudrait d'abord savoir si ton algorithme/programme termine sur toute entrée. Or ce problème (dit problème de l'arrêt) est indécidable dans le cas général. On peut cependant le faire pour certains algos, avec certaines contraintes. Il arrive ainsi qu'on arrive à prouver la correction (le fait que l'algorithme fasse bien ce qu'on lui demande) de certains programmes. Dans ce cas là, on pourrait surement obtenir également sa complexité en trafiquant le logiciel de preuve (type Coq) ce qui est loin d'être une mince affaire.
Ce qui peut être automatisé par contre, c'est le calcul de complexité d'un programme simple dans un langage impératif (genre C) dans lequel on ne fait pas d'allocation de mémoire dynamique, on n'utilise pas de boucle while, et où les boucles for ne modifient pas leur indice:
(genre for (i = 0; i < n; i++) {/*code qui ne modifie pas i*/})
Le calcul de complexité automatique est alors envisageable mais encore non-trivial.
une autre explication au fait que sa ne fonctionne pas encore c'est que ce serais la fin de notre travail !!
Répondre avec citation
Partager