您如何找到此类递归函数的空间复杂性？ [英] How do you find the space complexity of recursive functions such as this one?

问题描述

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

假设我们做了f（4）。我的想法是它将是O（2 ^ n），此后为了找到f（n-1）+ f（n-1），我们必须将f（n-1）= f（3）推到调用堆栈两次，然后f（2）调用堆栈的四倍，依此类推。但是，我从这本书中得到的书说是O（n）。

Suppose we did f(4). My thought was that it would be O(2^n), since then in order to find f(n-1) + f(n-1) we would have to push f(n-1) = f(3) to the call stack twice, and then f(2) four times the call stack, etc. However, the book I got this from says that is is O(n). Why is that true?

推荐答案

让我们想象一下对f（4）进行评估（您考虑的示例）。这是怎么回事。堆栈开始看起来像是

Let's imagine evaluating this for f(4) (the example you consider). Here's how it would go. The stack starts by looking like

I need to compute f(4)

然后，f（4）的计算返回到`f（3），堆栈看起来像

Then the calculation of f(4) recurs to `f(3), and the stack looks like

I need to compute f(4), so
 I need to compute f(3)

然后我们继续下降，最终到达

Then we keep going down and we eventually get to

I need to compute f(4), so
 I need to compute f(3), so
  I need to compute f(2), so
   I need to compute f(1), so
    I need to compute f(0)

然后，我们可以计算f（0）为1，最后一次通话返回。倒数第二个调用（计算f（1）的那个），然后想计算f（0）的第二个副本，堆栈转到：

Then, we can calculate f(0) as 1, and the last call returns. The penultimate call (the one to compute f(1)), then wants to compute the second copy of f(0), and the stack goes to:

I need to compute f(4), so
 I need to compute f(3), so
  I need to compute f(2), so
   I need to compute f(1), and although I've already computed the first f(0)=1, I still need to compute the second occurrence of f(0), so
    I need to compute f(0) (again)

然后返回，因此f（1）的计算可以返回，并且我们得到

Then that returns, and so the computation of f(1) can return, and we get to

I need to compute f(4), so
 I need to compute f(3), so
  I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0)

，然后堆栈变成：

I need to compute f(4), so
 I need to compute f(3), so
  I need to compute f(2), and although I've already computed the first f(1)=2, I still need to compute the second occurrence of f(0), so...
   I need to compute f(1)

，它将像以前一样继续计算f（1）。

and it will continue computing f(1) as before.

要点是，堆栈仅能达到n的深度，即使尽管（最终）将执行2 ^ n次操作。因此时间复杂度为O（2 ^ n），但空间复杂度仅为O（n）。

The point is that the stack only ever gets as deep as n, even though (ultimately) 2^n operations will be performed. So the time complexity is O(2^n) but the space complexity is only O(n).

这篇关于您如何找到此类递归函数的空间复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！