为什么空间复杂度递归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) + ...

Answer 2

因为执行recfunc(b) 之后 recfunc(a)，所以可以将用于recfunc(a)的相同空间重新用于recfunc(b)。它不会像时间一样累加。