python - 为什么空间复杂度递归S(n) = 2*S(n/2)中没有2*？

Question

from typing import List

def recfunc(xs: List[int]) -> List[int]:
    if len(xs) < 2:
        return xs
    a = list()
    b = list()
    for x in range(len(xs)):
        if x < len(xs) // 2:
            a.insert(0, x)
        else:
            b.insert(0, x)
    return recfunc(a) + recfunc(b)

此函数的空间复杂度为 S(n) = S(n/2) + c1*n + c2为 n>=2哪里 S代表空间和 c1,c2是一些常数。

为什么不是 S(n) = S(n/2)*2 + c1*n + c2 ?

Answer 1

在你的递归关系中，S(n)表示对 recfunc 的函数调用所占用的最大空间哪里n := len(xs) .

考虑这行代码:

return recfunc(a) + recfunc(b)

我们可以将其重写为:

a_result = recfunc(a)
b_result = recfunc(b)
return a_result + b_result

...不改变空间要求。

在任何给定时间，我们最多只需要 S(max(len(a), len(b))) 的空间。 ，也就是说，最多 S(n / 2) .因此:

S(n) = S(n / 2) + ...

另一方面，如果您使用 T(n) 上的递归关系测量时间复杂度。 ，那么上面的两个函数调用都会在某个时刻发生。所以我们会说:

T(n) = 2 * T(n / 2) + ...