为什么space复杂度递归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)

此函数的 space 复杂度是 S(n) = S(n/2) + c1*n + c2 对于 n>=2 其中 S 代表 space 和 c1,c2 是一些常量.

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

Answer 1

在您的递归关系中，S(n) 表示对 recfunc 的函数调用占用的最大值 space，其中 n := len(xs).

考虑代码行：

return recfunc(a) + recfunc(b)

我们可以将其重写为：

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

...不更改 space 要求。

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

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

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

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

Answer 2

因为 recfunc(b) 在 recfunc(a) 之后被执行，所以用于 recfunc(a) 的 space 可以重复使用recfunc(b)。它不像时间那样累加。