Comment calculer la complexité algorithmique des fonctions Python?
Lorsque requis pour démontrer l'efficacité de l'algorithme, nous avons besoin de montrer la complexité algorithmique des fonctions - Big O et ainsi de suite. Dans le code Python, comment pouvons-nous montrer, ou de calculer des limites de fonctions?
En général, il n'y a aucun moyen de le faire par programmation (vous exécutez dans le problème de l'arrêt).
Si vous n'avez aucune idée de par où commencer, vous pouvez avoir un aperçu de la façon dont une fonction qui permet d'effectuer à l'exécution de certains tests (par exemple, à l'aide de la time module), avec les contributions de différentes tailles. Vous pouvez même recueillir suffisamment de données pour former une suspicion sur ce que l'exécution pourrait être. Mais ce ne sera pas vous donner une réponse rigoureuse - pour cela, vous devez prouver mathématiquement que votre soupçonné lié est vrai, en fait.
Par exemple, si je suis en train de jouer avec une fonction de tri et d'observer que le temps est en augmentation à peu près proportionnellement au carré de la taille de saisie, je pourrais suspect que la complexité de ce genre est O(n**2). Mais cela ne constitue pas une preuve - en particulier, certains algorithmes qui fonctionnent bien dans des conditions normales d'entrées pathologique entrées résultant dans de très mauvaises performances.
De prouver que la limite est en fait O(n**2), j'ai besoin de chercher à ce que l'algorithme est en train de faire dans le pire des cas - dans cet exemple, j'ai peut-être l'analyse d'un tri de sélection, qui, à plusieurs reprises balaye l'ensemble de la partie non triée de la liste et choisit le plus bas des ménagères de nombre. Il devrait être évident que je suis à l'examen de quelque chose comme n*(n-1) == O(n**2) éléments. Si l'examen des éléments est une constante de temps de l'opération, et de placer l'élément final de l'endroit correct est pas pire que O(n**2), il s'ensuit que l'ensemble de mon algorithme est O(n**2).
Si vous essayez d'avoir le big O la notation de vos fonctions, vous avez probablement besoin des variables de garder une trace des choses comme:
le moteur d'exécution; le nombre de comparaisons; le nombre d'itérations; etc. Ainsi que de certains calculs étudier la façon dont ceux-ci correspondent à la taille de vos données.
Il est probablement préférable de le faire manuellement, d'abord, de sorte que vous pouvez vérifier votre compréhension de l'algorithme.
En général, il n'y a aucun moyen de le faire par programmation (vous exécutez dans le problème de l'arrêt).
Si vous n'avez aucune idée de par où commencer, vous pouvez avoir un aperçu de la façon dont une fonction qui permet d'effectuer à l'exécution de certains tests (par exemple, à l'aide de la
timemodule), avec les contributions de différentes tailles. Vous pouvez même recueillir suffisamment de données pour former une suspicion sur ce que l'exécution pourrait être. Mais ce ne sera pas vous donner une réponse rigoureuse - pour cela, vous devez prouver mathématiquement que votre soupçonné lié est vrai, en fait.Par exemple, si je suis en train de jouer avec une fonction de tri et d'observer que le temps est en augmentation à peu près proportionnellement au carré de la taille de saisie, je pourrais suspect que la complexité de ce genre est
O(n**2). Mais cela ne constitue pas une preuve - en particulier, certains algorithmes qui fonctionnent bien dans des conditions normales d'entrées pathologique entrées résultant dans de très mauvaises performances.De prouver que la limite est en fait
O(n**2), j'ai besoin de chercher à ce que l'algorithme est en train de faire dans le pire des cas - dans cet exemple, j'ai peut-être l'analyse d'un tri de sélection, qui, à plusieurs reprises balaye l'ensemble de la partie non triée de la liste et choisit le plus bas des ménagères de nombre. Il devrait être évident que je suis à l'examen de quelque chose commen*(n-1) == O(n**2)éléments. Si l'examen des éléments est une constante de temps de l'opération, et de placer l'élément final de l'endroit correct est pas pire queO(n**2), il s'ensuit que l'ensemble de mon algorithme estO(n**2).OriginalL'auteur atomicinf
Prendre un coup d'oeil à the big O notation pour les différents python opérations ici:
https://wiki.python.org/moin/TimeComplexity
C'est une bonne remise pour le collège choses ainsi:
http://www.nikhilgopal.com/2012/04/refresher-on-big-o-notation-python.html
Et enfin un bon exemple concret ici:
Python complexité (run-time)
OriginalL'auteur Rami
Si vous essayez d'avoir le big O la notation de vos fonctions, vous avez probablement besoin des variables de garder une trace des choses comme:
le moteur d'exécution; le nombre de comparaisons; le nombre d'itérations; etc. Ainsi que de certains calculs étudier la façon dont ceux-ci correspondent à la taille de vos données.
Il est probablement préférable de le faire manuellement, d'abord, de sorte que vous pouvez vérifier votre compréhension de l'algorithme.
OriginalL'auteur Dylan