Почему нет 2 * в повторяемости сложности пространства S (n) = 2 * S (n / 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

Поскольку recfunc(b) выполняется после recfunc(a), поэтому то же пространство, которое использовалось для recfunc(a), можно повторно использовать для recfunc(b). Это не складывается, как время.

Answer 2

В вашем рекурсивном отношении 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) + ...