利用时间模块测试复杂度

Question

我怀疑递归的时间复杂性。 假设我需要使用递归查找列表中的最大数字，我得出的结论是：

def maxer(s):
    if len(s) == 1:
        return s.pop(0)
    else:
        if s[0]>s[1]:
            s.pop(1)
        else:
            s.pop(0)
        return maxer(s)

现在，为了测试具有多个输入的函数并找出其时间复杂度，我调用了该函数，如下所示：

import time
import matplotlib.pyplot as plt
def timer_v3(fx,n):
    x_axis=[]
    y_axis=[]
    for x in range (1,n):
        z = [x for x in range(x)]
        start=time.time()
        fx(z)
        end=time.time()
        x_axis.append(x)
        y_axis.append(end-start)
    plt.plot(x_axis,y_axis)
    plt.show() 

作为一个粗略的估计，检查这样的复杂性是否存在根本性的缺陷？如果是这样，我们如何快速检查时间复杂性

Answer 1

假设s是一个列表，那么函数的时间复杂度是O（n²）。当您从列表的开头开始pop时，剩余的元素必须左移一个空间以“填充”间隙；这需要O（n）次时间，并且您的函数从列表的开始弹出O（n）次。因此，总体复杂度为O（n*n）=O（n²）

---

不过，您的图形看起来不像一个二次函数，因为O（n²）的定义意味着它只需要具有n>；的二次行为；n₀，其中n₀是任意数。1000不是一个很大的数字，尤其是在Python中，因为较小输入的运行时间主要是解释器开销，而O（n）pop操作实际上非常快，因为它是用C编写的。因此，这不仅是可能的，而且很可能是n<；1000太小，无法观察到二次行为

问题是，您的函数是递归的，因此它不一定要在足够大的输入下运行，以观察二次运行时间。太大的输入将使调用堆栈溢出，或使用太多内存。因此，我使用while循环将递归函数转换为等价的迭代函数：

def maxer(s):
    while len(s) > 1:
        if s[0] > s[1]:
            s.pop(1)
        else:
            s.pop(0)
    return s.pop(0)

这严格来说比递归版本快，但它具有相同的时间复杂性。现在我们可以走得更远；我测量了n=3000000的运行时间

这看起来很像一个二次函数。此时您可能会说，“啊，@kaya3已经向我展示了如何正确地进行分析，现在我看到函数是O（n²）。”，但这仍然是错误的。测量实际运行时间（即dynamic analysis）仍然不是分析函数时间复杂性的正确方法。无论我们测试的n有多大，n₀仍然可能更大，我们无法知道

因此，如果你想找到一个算法的时间复杂度，你必须通过static analysis来计算，就像我在这个答案的第一段中（粗略地）做的那样。你不会通过做动态分析来节省自己的时间；如果您有相关知识，只需不到一分钟的时间就可以阅读您的代码并查看它是否执行了O（n）次O（n）次操作。因此，开发这些知识绝对值得