Space求和函数递归实现的时间复杂度

Question

谁能告诉我以下代码的 space 和时间复杂度？我知道时间复杂度应该是 O(n) 因为函数被调用了 n 次，而 space 复杂度至少是 O(n) （因为堆栈 space），但是确实传递了一个[1:] 函数导致 space 复杂性增加？我认为 a[1:] 将创建 a 的新副本，同时省略第一个元素，对吗？

def sum(a):
    if len(a) == 1:
        return a[0]
    return a[0] + sum(a[1:])

Answer 1

时间复杂度类似于 theta(n^2)，因为每次执行 a[i:] 时，基本上都是将列表从 i 复制到末尾，因此您必须遍历它。至于 space 复杂性，应用程序堆栈将包含您将调用的所有列表，首先是一个包含 n 个元素的列表，然后是 n-1 等等，直到 1，您将在此处开始清空堆栈。所以你最终也会得到一个 theta(n^2) 的复杂度。

Answer 2

作为递归函数，如果不应用 tail-call 优化，在这种情况下，考虑到它在内存上的执行，它肯定具有至少 O(n) 的 space 复杂度堆。但是让我们进一步分析一下：

时间复杂度

我们知道sum是递归的，它的停止条件是输入数组为单长时。所以我们知道 Sum 在最坏的情况下至少会被调用 O(n) 次，考虑到大小为 n 的输入数组。考虑递归是什么，我。即，循环.

然而，在函数内部，我们有一个切片操作。切片操作l[a:b]是O(b-a)，所以这个操作在第一个运行中会有O(n-1)的复杂度，在第二个运行中会有O(n-2)的复杂度，等等。我们从根本上考虑，它会执行整个数组的复制。此函数的总体时间复杂度应为 O(n^2)，因为它为大小为 n.

的数组中的每个项目创建一个切片

Space复杂度

现在说说记忆中的space。

len(a) == 1

这里我们从 len(a) 的 return 值中得到一个副本。

return a[0]

&

    return a[0] + sum(a[1:])

在上面的两行中，我们将有另一个值的副本，该值将存储到函数的 return 地址中。该切片还具有 O(n) space 复杂度。

看到这一点，并考虑到编译器没有应用重大的优化优化，例如 reduction，我们说这个函数的 space 复杂度是 O(n)因为它将为每个输入生成常量的副本，并且会在大小为 n.

的数组中执行切片操作

既然我们一开始就说递归就像一个循环，考虑到没有尾调用优化，整个函数在最坏的情况下会执行n次。程序将增加函数的内存堆栈，直到它达到停止条件，直到它最终可以从调用堆栈中提取 'pop' return 值。因此，总 space 复杂度也是 O(n*log n)（因为每次执行输入数组都较小）。

Ps:

我还认为 len(a) 具有 O(1) 时间复杂度，根据 this。

Space求和函数递归实现的时间复杂度

Space and time complexity of recursive implementation of summation function

python

performance

recursion

time-complexity

space-complexity