python - 如何计算 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)。

Answer 2

如果您尝试为自己的函数获取大 O 表示法，您可能需要变量来跟踪以下内容：runTime；比较次数；迭代次数；等等，以及一些调查这些如何对应于您的数据大小的计算。最好先手动执行此操作，这样您可以检查您对算法的理解。