Problème d’évaluation d’algorithme

[invite57f2391b]

Bonjour,

Je suis nouveau sur le forum et j’ai une petite question à vous posez !

Je me suis intéressé récemment au problème du millénaire n=np ou n != np, j’ai réussi à faire un algorithme qui résout des problèmes de type SAT or je ne connais pas sa complexité (polynomial, exponentielle), le problème c’est que cet algorithme je l’ai écrit sous le langage de programmation Python (et j’utilise des fonction propres au langage (len(), set(), type()) dont je ne connais pas la complexité), je voulais savoir si il existe un langage primaire (utilisé par les mathématiciens) dans lequel je pourrais écrire mon algorithme pour pouvoir calculer facilement sa complexité !

Cordialement
-----

[pm42]

On trouve facilement la complexité des fonctions dont tu parles et pour ton programme comme pour elles, il est facile de l'évaluer : tu exécutes avec des données d'une certaine taille, puis du double, puis du double et tu vas vite voir si c'est linéaire, polynomial ou exponentiel.

Sinon, pour des algos simples, on peut aussi déduire la complexité en analysant rapidement d'autant plus que les fonctions que tu indiques sont toutes plutôt du temps constant.

Parce que les autres méthodes vont être à mon humble avis plus lourdes, complexes et il y a des problèmes théoriques qui s'opposent à ce qu'elles soient générales notamment le fait qu'on ne peut pas décider si un programme s'arrête ou pas.

[GBZM]

Bonjour,

Pour commencer, le problème c'est P=NP (et pas n=np) .