Space 递归函数的复杂度

Question

给定以下函数：

int f(int n) {
  if (n <= 1) {
    return 1;
  }
  return f(n - 1) + f(n - 1);
}

我知道大O的时间复杂度是O(2^N)，因为每次调用都会调用函数两次

我不明白的是为什么 space/memory 复杂度是 O(N)？

Answer 1

解决这类问题的一个有用方法是思考 recursion tree。递归函数识别的两个特征是：

树的深度（总共return条语句将被执行到基本情况）
树的宽度（总共递归函数调用

我们这个案例的递推关系是T(n) = 2T(n-1)。正如您正确指出的那样，时间复杂度是 O(2^n)，但让我们看看它与我们的循环树的关系。

      C
     / \         
    /   \      
T(n-1)  T(n-1)

            C
       ____/ \____
      /           \
    C              C   
   /  \           /  \
  /    \         /    \
T(n-2) T(n-2) T(n-2)  T(n-2)

此模式将一直持续到我们的基本情况如下图所示：

对于每个连续的树级别，我们的 n 减少 1。因此我们的树在到达基本情况之前将具有 n 的 深度。由于每个节点都有 2 个分支，并且我们有 n 个总级别，因此我们的节点总数为 2^n，使我们的时间复杂度为 O(2^n)。

我们的内存复杂度由return语句的数量决定，因为每个函数调用都将存储在程序堆栈中。概括地说，递归函数的内存复杂度是O(recursion depth)。正如我们的树深度所示，我们将有 n 总共 return 个语句，因此内存复杂度为 O(n).

Answer 2

以下是我的看法：

诱惑说space复杂度也会是O(2^N)，因为毕竟每次O(2^N)次递归调用都要分配内存，正确的？（不对）
实际上，每次调用都会添加 together/collapsed 值，因此所需的 space 只是从基数开始的每次调用的结果case on up，形成数组 [f(1), f(2), f(3) ... f(n)]，换句话说就是 O(n) memory

Answer 3

考虑到不同的功能，可以更好地解释这一点
f(n) = f(n-1) + f(n-2)
f(0) =0, f(1)=1

这将导致以下 f(4)

的计算树

f(4)
f(3) f(2)
f(2) f(1) f(1) f(0)
f(1) f(0)

系统可以处理重复存储堆栈等于深度的计算（存储单元为f(0)、f(1)、f(2)、f(3)和f(4) ).虽然运行时需要考虑每个节点的所有操作（加法或 return 语句）——因此是节点 none 的一个因素。

Answer 4

我在两篇文章中找到了明确的答案。

第一个

在这个 article ，它告诉我为什么 space 复杂度是 O(n).

但我也很困惑，为什么 the stack frames 一次只有 f(5) -> f(4) -> f(3) -> f(2) -> f(1) 而没有 f(5) -> f(4) -> f(3) -> f(2) -> f(0) 和其他人。

The Fibonacci tree 图片：

然后我终于在第二篇文章中找到了答案，解决了我的困惑。

第二

在这 article 很有帮助。你可以在这里看到详细信息。

The stack frames 图片：

谢谢。

Answer 5

递归问题我们可以想成是用栈来实现的，所以如果第一个函数调用自己，第二个函数pause，然后遍历末尾，一个一个的入栈，完成后会return 并从最顶层的堆栈中一个一个地删除，然后第二个函数恢复并遍历末尾并添加到堆栈的最顶层，并在 returning 时间删除。但是它使用相同的堆栈，并且在相同的堆栈下最多需要 n space 所以使用 space 复杂度 O(n).

Space 递归函数的复杂度

Space complexity of recursive function

big-o

space-complexity

第一个

第二