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

Question

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

- coolharsh55

Answer 1

一般而言，这无法通过程序实现（会遇到停机问题）。

如果您不知道从何处入手，可以通过运行一些基准测试（例如使用 time 模块）来了解函数的性能如何，输入各种大小的数据。甚至可以收集足够的数据以形成对运行时间的猜测。但这并不会给出严格的答案——为此，您需要在数学上证明您怀疑的边界确实是真实的。

例如，如果我正在玩一个排序函数，并观察到时间大致与输入大小的平方成比例增加，那么我可能会猜测这个排序的复杂度是 O(n**2)。但这并不能构成证明——特别地，某些算法在典型输入下表现良好，但在有些输入下则表现非常差。

要证明这个界限实际上是 O(n**2)，我需要查看算法在最坏情况下的操作。在这个例子中，我可能正在分析选择排序，该算法重复扫描整个未排序部分的列表并选择最小的未排序数字。很明显，我正在考虑诸如 n*(n-1) == O(n**2) 元素之类的东西。如果检查元素是一个常量时间操作，并且将最终元素放置在正确的位置上也不比 O(n**2) 更糟，那么我的整个算法就是 O(n**2)。

- atomicinf

Answer 2

如果您想获取自己函数的大O符号，您可能需要跟踪变量，例如： 运行时间；比较次数；迭代次数等。以及一些计算来研究它们如何与数据大小相对应。 最好先手动完成此操作，以便您可以检查算法的理解。

- Dylan