此函数的时间和 space 复杂度

Question

def f3(n):
   if n <= 1:
      return 1
   L = [i for i in range(n)]
   return 2 * f3(n // 2) + 1

我正在尝试计算这个函数的时间和 space 复杂度，关于最后一部分我有一个非常重要的问题 2*f3(n//2)：我们认为它是 2 个递归调用，还是就一个？

以下是我的计算方式：T(n)=n+2T(n//2)=n+2*[n/2 + 2t(n//4)]=2n+4T(n//4)=...=kn + 2^k*T(n/(2^k)) 在 n/(2^k) = 1 然后 n = 2^k、log(n)=k 处停止。所以我们有 log(n) 次迭代，通过代回我们得到 nlog(n)+n*1 这意味着 O(nlog(n)) 的时间复杂度，并且由于我们使用的是列表理解，所以 space 复杂度也是如此。

但是现在再看2*f3(n//2)，是不是和f3(n//2)+f3(n//2)一样，还是我大错特错了？

因为如果只调用一次函数，时间和 space 复杂度将是 O(log(n))，我猜。

如果对我的问题有任何解释，我将不胜感激，并且很乐意听到有关我的回答的任何反馈和提示。

Answer 1

递归调用的数量是O(lg n)，但是你还需要考虑每个work那些电话确实如此。这项工作（计算 L）与输入的大小成线性关系。因此，总时间复杂度本质上是总和 n + n//2 + n//4 + ... + 1，您应该能够将其验证为 O(n)。

space 的复杂性取决于您需要用 L 做什么。如果在递归调用期间或之后不需要它，则可以通过在递归调用之前删除它来降低 space 复杂性。

此函数的时间和 space 复杂度

Time and space complexity of this function

python

time-complexity

space-complexity