Python 是否有工具可以自动计算函数的 Big-O 复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/31284899/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Is there a tool to automatically calculate Big-O complexity for a function
提问by Igor Barinov
While studying algorithms and data structures I manually evaluate BigO complexity for my script. Is there a way, let say a button in any Python IDE or a package, to calculate BigO for any given function or a program?
在研究算法和数据结构时，我手动评估了脚本的 BigO 复杂性。有没有办法，比如任何 Python IDE 或包中的一个按钮，来计算任何给定函数或程序的 BigO？
UPDATE:
更新：
Let's say I have
假设我有
def print_first_element(a):
print a[0]
why I can't write the analyzer which will say me ok you access the array (list) by index and its O(1), or
为什么我不能编写分析器，它会说我可以通过索引及其 O(1) 访问数组（列表），或者
def print_all_element_of_list(a):
for i in a:
print i
ok you have full scan so the complexity is O(n)
好的，你有完整的扫描，所以复杂度是 O(n)
and so forth
等等
回答by ReyCharles
It's not possible in general. Here's one python program that can compute the complexity for some program: https://github.com/Mortal/complexity
一般是不可能的。这是一个可以计算某些程序复杂度的 Python 程序：https: //github.com/Mortal/complexity
回答by ferhat elmas
Unfortunately, infeasible. See Halting Problem.
不幸的是，不可行。请参阅停止问题。
