任何人都可以建议以下代码的时空复杂性吗？ 我知道时间复杂度应为O（n），因为该函数被调用了n次，并且空间复杂度至少为O（n）（由于堆栈空间），但是确实将a [1：]传递给函数会导致空间复杂度增加了吗？我认为a [1：]将在省略第一个元素的同时创建一个new的副本，对吗？
def sum(a):
if len(a) == 1:
return a[0]
return a[0] + sum(a[1:])
- 积分
0 - 话题
0 - 评论
3284 - 注册排名
1976
任何人都可以建议以下代码的时空复杂性吗？ 我知道时间复杂度应为O（n），因为该函数被调用了n次，并且空间复杂度至少为O（n）（由于堆栈空间），但是确实将a [1：]传递给函数会导致空间复杂度增加了吗？我认为a [1：]将在省略第一个元素的同时创建一个new的副本，对吗？
def sum(a):
if len(a) == 1:
return a[0]
return a[0] + sum(a[1:])
时间复杂度类似于theta（n ^ 2），因为每次执行a [i：]时，您基本上都会将列表从i复制到末尾，因此您必须对其进行迭代。至于空间的复杂性，应用程序堆栈将包含所有要调用的列表，首先是包含n个元素的列表，然后是n-1，依此类推，直到1，然后开始清空堆栈。因此，您最终也将面临theta（n ^ 2）的复杂性。
As a recursive function, if no tail-call optimizations are applied, it will certainly have a space complexity of at least
O(n)in this case, considering its execution on the memory stack. But let us analyze it further:时间复杂度
We know that sum is recursive and its stop criteria is when the input array is single length. So we know that
Sumwill be called at leastO(n)times in the worst-case scenario, considering an input array of sizen. Consider the recursion for what it is, i. e., a loop. Inside the function there aren't any other loops I noticed, so time complexity isO(n)空间复杂度
现在谈论内存中的空间。
在这里，我们从len（a）的返回值得到一个副本。
和
在上面的两行中，我们将有一个值的另一个副本，该副本将存储在函数的返回地址中。
Seeing this, and considering no major-breaking optimizations are being applied by the compiler, such as a reduction, we say that the space complexity of this function is
O(1)because it will make a constant number of copies for each input.Since we said in the beginning that recursion is like a loop, considering no tail-call optimizations, this constant copy operations will be performed
ntimes in the worst-case scenario. The program will increase the function's memory stack until it reaches the stop criteria, until it can finally 'pop' return values from the stack of calls. The total space complexity is thusO(n).附：
就我而言，a [1：]是切片操作，不会复制整个数组。