这个项目的空间复杂度是多少

Question

def howsum(target, array):


    if target == 0:
        return []

    if target<0:
        return None

    for num in array:

        remainder = target-num

        sol = howsum(remainder, array)

        if sol!=None:
            return [num]+sol


    return None

print(howsum(8,[5,3,2]))
print(howsum(7,[3,2]))
print(howsum(7,[2,4]))
print(howsum(7,[5,3,4,7]))

我在一个关于动态编程的视频中看到了这段代码。我怀疑这段代码的空间复杂性。在该视频中提到，程序的空间复杂度为O（m），因为它调用m次程序（递归）。但我怀疑的是，在最坏的情况下，每个函数调用将返回一个大小为m的数组，在最坏的情况下，函数调用的数量将是m，如果是这种情况，那么每个函数调用应该使用大小为m的数组，那么空间复杂度将是O（m）而不是O（m^2）

请任何人帮帮我。我是这个编程领域的新手

Answer 1

在我看来，最糟糕的空间复杂性将是O(target)。所以这个视频实际上是关于O(m)的，如果它的意思是m = target。举个简单的例子，我想实际最坏的情况是howsum(N, [1])。您将需要N调用来计算结果，并将返回大小为N的数组。每个调用只向该数组添加1个元素。当然，我假设array是一个整数数组，其不同值高于0