Réponse
Un algorithme est polynomial (a un temps dexécution polynomial) si pour quelques $ k, C > 0 $, son temps dexécution sur les entrées de taille $ n $ est au plus $ Cn ^ k $. De manière équivalente, un algorithme est polynomial si pour certains $ k > 0 $, son temps dexécution sur des entrées de taille $ n $ est $ O (n ^ k) $. Cela inclut linéaire, quadratique, cubique et plus. Dun autre côté, les algorithmes avec des temps dexécution exponentiels ne sont pas polynomiaux.
Il y a des choses entre les deux – par exemple, lalgorithme le plus connu de factorisation sexécute dans le temps $ O (\ exp (Cn ^ {1 / 3} \ log ^ {2/3} n)) $ pour une constante $ C > 0 $; un tel temps dexécution est appelé sous-exponentiel . Dautres algorithmes pourraient sexécuter dans le temps $ O (\ exp (A \ log ^ C n)) $ pour certains $ A > 0 $ et $ C > 1 $, et on les appelle quasi-polynôme . Un tel algorithme a été récemment revendiqué pour le log discret sur de petites caractéristiques.
Commentaires
- Voir aussi ici .
- Que sont k et C?
- Ce sont des paramètres.
- Les algorithmes à temps constant sont donc considérés comme polynomiaux, nest-ce pas?
- Les algorithmes à temps constant sont un cas particulier des algorithmes à temps polynomial.
Réponse
Lexécution dun algorithme peut prendre un certain temps de calcul. Cela dépend principalement de la complexité de lalgorithme. Les informaticiens ont trouvé un moyen de classer lalgorithme en fonction de son comportement en fonction du nombre dopérations quil doit effectuer (plus dopérations prennent plus de temps).
Une de cette classe montre une complexité temporelle polynomiale. Autrement dit, la complexité opérationnelle est proportionnelle à $ n ^ c $ tandis que n est la taille de lentrée et c est une constante. De toute évidence, le nom vient de $ n ^ c $ qui est un polynôme .
Il existe dautres « types » dalgorithmes qui prennent un temps constant quelle que soit la taille de lentrée. Certains prennent 2 $ ^ n $ de temps (oui, vraiment slllooooww la plupart du temps).
Je lai un peu simplifié pour le profane et jai peut-être introduit des erreurs. Alors lisez plus https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time
Commentaires
- Jai lu sur Wolfram que les algorithmes de temps polynomiaux sont dits " rapides " . Cependant, jentends beaucoup de gens dire préférer les algorithmes de temps logarithmiques ou linéaires aux algorithmes de temps polynomiaux. Suis-je mal compris lutilisation du mot " fast "?
- Logarithmique et linéaire sont également polynomiaux. Je pense que ' rapide ' signifie probablement quelque chose comme ' beaucoup plus susceptible dêtre pratique pour utilisation réelle '.
Réponse
En termes simples, il le temps dexécution de votre algorithme.
Lordre des algorithmes (croissance) peut être en Big-oh (O), little-oh (o), omega (Ω) ou theta (Θ).
Si vous rencontrez des problèmes pour calculer le RR, veuillez consulter les questions que jai posées auparavant et voter si vous comprenez.
Supposons que vous ayez une boucle for:
for(i=1 to n) x++ Lordre ou la complexité temporelle de ce morceau de code est: O (n)
Pourquoi big-oh? Parce que nous voulons le pire des cas où ce morceau de code sexécute.
Lisez ici (ceux-ci définissent la complexité dun algorithme et vous informe de la façon dont les algorithmes sont exécutés en temps polynomial):
http://en.wikipedia.org/wiki/NP_(complexity) http://en.wikipedia.org/wiki/NP-complete http://en.wikipedia.org/wiki/NP-hard Résumé:
http://www.multiwingspan.co.uk/a23.php?page=types
Commentaires
- Cela ne ' t répond exactement à la question: temps polynomial nest pas " la durée dexécution de votre algorithme ". Au lieu de cela, lexécution dun algorithme peut être polynomiale, et ainsi de suite. Vous pourriez améliorer la réponse en la rendant plus précise. Par exemple, avons-nous vraiment besoin de lire 3 articles Wikipédia sur quelque chose, ou avons-nous vraiment besoin de savoir quoi que ce soit sur Big Oh?