该代码的空间复杂度是多少？ [英] What is the space complexity of this code?

问题描述

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

我知道时间复杂度为 O（2 ^ n）我理解为什么。

I know that the time complexity is O(2^n) and I understand why.

但是我不明白为什么空间复杂度是 O（n ）。
有人告诉我，这是因为在任何给定时间只有 n 个节点，但这对我来说没有意义。

But I don't understand why the space complexity is O(n). I was told that it's because at any given time there are only n nodes, but it doesn't make sense to me.

推荐答案

因为第二个 f（n-1）不能运行，直到第一个完成（反之亦然-两种方法都一样）。第一次调用将递归 n 次，然后所有返回，因此将总共推送 n 个堆栈框架。然后第二个调用将执行相同的操作。

Because the second f(n-1) can't run until the first one completes (or vice versa -- it's the same either way). The first call will recurse n times, then all those will return, so that will push a total of n stack frames. Then the second call will do the same thing.

因此，在递归中，它获得的水平永远不会超过 n ，这是造成空间复杂性的唯一原因。

So it never gets more than n levels deep in the recursion, and that's the only contributor to space complexity.

这篇关于该代码的空间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！