python - 以下算法的空间复杂度如何 O(logn)？

Question

以下是一段 python 代码，用于使用 Goodrich 和 Tamassia 一书中的二进制递归查找元素列表的总和。

    def binary_sum(S, start, stop):
  """Return the sum of the numbers in implicit slice S[start:stop]."""
        if start >= stop:                      # zero elements in slice
            return 0
        elif start == stop-1:                  # one element in slice
            return S[start]
        else:                                  # two or more elements in slice
            mid = (start + stop) // 2
            return binary_sum(S, start, mid) + binary_sum(S, mid, stop)

所以书中说:

“范围的大小在每次递归调用时被分成两半，并且所以递归的深度是1+logn。因此，二进制和使用 O(logn)额外空间量。然而，运行时间二进制和是 O(n)，因为有 2n−1 个函数调用，每个函数调用都需要常数时间。"

据我了解，该算法的空间复杂度为 O(logn)。但是既然是2n-1个函数调用，python岂不是要为每个函数保留2n-1个不同的激活记录？因此，空间复杂度应该是 O(n)。我错过了什么？

Answer 1

it is making 2n-1 function calls

不是所有的人都在同一时间。函数调用有开始和结束。

wouldn't python have to keep 2n-1 different activation records for each function?

只有活跃的激活记录才需要占用空间。在任何给定时间都有 O(recursion_depth)。