为什么下面的代码只有 space 的复杂度 O(N)？

Question

这直接取自 Gayle Lakmaan McDowell 的破解编码采访。

她列出了以下代码：

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

她对为什么时间复杂度是O(2^n)有一个清晰的解释，但是为什么这里的space复杂度只有O(N)？

Answer 1

space 复杂性考虑到了调用堆栈的使用。该函数将在返回前调用自身 O(N) 次，因此调用堆栈将 O(N) 深。

更新（感谢@MatthewWetmore）：

澄清一下，f(n-1) + f(n-1); 表达式中的两个递归调用不是并行执行的。第一个调用完成消耗线性堆栈使用，然后是第二个调用，消耗相同的堆栈大小。所以 space 没有加倍，这与 running-time 消耗不同（显然每次调用都会累积）。

Answer 2

它在系统堆栈中使用了那么多 space 来进行函数调用像 F(5) 会调用 F(4)，F(4) 会调用 F(3)

F(5)->F(4)->F(3)->F(2)->F(1)->return值将按相反顺序关闭函数

所以为了计算这个 space 被分配在 F(5) 5 堆栈 space 所以对于 F(n) ，space 将是 O(N)

Answer 3

O 表示法是一种渐近表示法。这意味着该符号表示完成算法的时间永远不会超过特定限制并且可以低于特定限制，但这没有指定，它是有界的。算法的时间复杂度取决于输入的大小。这可以是 {1} 一个数字的输入或 {1,2} 是前一个输入大小的两倍的输入。这就是 n 的意思 O(n)。这意味着该算法具有线性复杂性，这意味着完成该算法的时间将是 n * 某个常数或 C * n。
您可能会问自己，我们如何确定 C 好，这就是为什么我们使用渐近表示法我们可以省略 C 的确切值，这很有用，因为我们可能会看到一个算法可以有一个 C，它根据输入的顺序或一些其他情况。您可能会看到最好情况和最坏情况，其中复杂度为 Cn，最坏情况为 Cnlogn，在这种情况下，我们说算法具有 O(nlogn) 复杂度，这是因为我们以最坏情况为边界。在这种情况下，我们仍然省略了 C，并且我们省略了最佳情况 Cn。您可以考虑阅读算法书籍以获取更多信息，例如计算机编程艺术书籍 1 或 Algorithms by Robert Sedgewick。 Sedgewick 的书使用 Java 并且非常容易理解。

Space 复杂性的工作方式相同，但这次我们谈论的是内存 space，有一种称为动态规划的技术，这种技术存储以前的结果，以便您以后可以将它们用作解决方案到子问题。这样我们多次跳过对子问题进行计算所花费的时间，但是解决问题所需的内存量增加了经典示例是Change-making problem。您存储了许多解决方案，并且 space 它占用的系统内存增加了。该问题具有线性 space 复杂性，因为解决该问题所需的内存量表现为函数 Cn。

举个例子，这个函数使用了n，它在内存中可以说是一个space，1常量是另一个，所以我们可以说内存中的space就是1+n；在这种情况下，我们说线性函数有一个位移 a 线性函数是 Cn + a 其中 C = 1 和 a = 1。仍然是线性函数。 n 来自递归，因为我们将需要 n space 在内存中存储 n 个数字，因为递归一直下降到 1。例如，假设 n = 3.

第一次我们在内存中有 3，因为它向下递归，我们将 2 存储在内存中，最后存储 1，我们可以说 1 是否已经在内存中，因为 1 所在的 space 可能在堆栈上或堆上。这就是我们使用 O 表示法的原因，这取决于架构实现。因此，虽然有时复杂度可以是 1+n，但也可以是 n，但说 O(n) 我们涵盖了这两种情况。

此外，如果您对该行有疑问：

f(n-1) + f(n-1);

根据体系结构，你可能有一个堆栈，或者你可以将它们发送到主内存（没有想到这种体系结构的例子）并让垃圾收集器清理超出范围的引用，它仍然是线性 space 存储 3 * 2、2 * 2、1 * 2。在这种情况下，它将是 2n+1 或 2n。还是线性的。但我怀疑你看到这样的东西最有可能你会有一个堆栈，一旦递归 return 它就会开始从堆栈中弹出所有变量，最多使用 1+n 或 n+1。

为什么下面的代码只有 space 的复杂度 O(N)？

Why does the following code only have space complexity O(N)?

algorithm

time-complexity

space-complexity