如何计算Python函数的算法复杂度？

Question

当需要显示算法的效率时,我们需要显示函数的算法复杂性 - 大O等.在Python代码中,我们如何显示或计算函数的边界？

Answer 1

通常,没有办法以编程方式执行此操作(您遇到暂停问题).

如果您不知道从哪里开始,您可以通过运行一些time具有各种大小输入的基准(例如使用模块)来了解函数的执行方式.您甚至可以收集足够的数据,以怀疑运行时可能是什么.但是这不会给你一个严格的答案 - 为此,你需要在数学上证明你的可疑界限实际上是正确的.

例如,如果我正在使用排序功能并观察时间大致与输入大小的平方成比例增加,我可能会怀疑这种复杂性O(n**2).但这并不构成证据 - 特别是一些在典型输入下表现良好的算法具有病理输入,导致性能非常差.

为了证明边界实际上O(n**2),我需要看看算法在最坏的情况下做了什么 - 在这个例子中,我可能正在分析一个选择排序,它反复扫描列表的整个未排序部分并选择最低未分类数.很明显,我正在研究类似n*(n-1) == O(n**2)元素的东西.如果检查元素是一个恒定时间操作,并且将最终元素放在正确的位置也不会比O(n**2)这更差,那么我的整个算法就是如此O(n**2).