python - 理解这个 python 函数的复杂性

Question

函数 f(L) 的复杂度(“大 O”表示法)是多少，其中 n 是 L 的长度？我可以理解为内部函数的运行时间是恒定的。因此它是O(n)吗？

该函数取自《CS Python入门》类(class)中的一次测试。

def f(L):
    def f_helper(L,i):
        if i:
            return f_helper([L,L], i-1) + f_helper([L,L], i-1)
        return len(L)
    return f_helper(L,3)

Answer 1

首先，注意基本情况，本质上是

if i == 0:
    return len(L)

其中 L 是来自上一个实例的 [L, L]。 如果 L 最初是一个列表、元组、字符串...那么 [L, L] 将是一个长度为 2 的列表，所以 len(L) 将是 O(1)。

接下来，您是否有任何可以作为 L 传递的对象，其中 [L, L] 不是一对对输入参数的引用？如果不是，那么每个实例都只是一对 O(1) 的调用。

要观看此操作，请在输入函数时添加一个简单的跟踪语句:

print("ENTER", i, L)

并观察您在每次函数调用时得到的结果。

这足以让您找到答案吗？