递归函数的空间复杂度 [英] Space complexity of recursive function

问题描述

给出以下功能:

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

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

I know that the Big O time complexity is O(2^N), because each call calls the function twice.

我不明白为什么空间/内存复杂度是O(N)?

What I don't understand is why the space/memory complexity is O(N)?

推荐答案

解决这些类型问题的一种有用方法是考虑

A useful way to approach these types of problems is by thinking of the recursion tree. The two features of a recursive function to identify are:

1. 树的深度(在基本情况下将执行总共 个返回语句 )
2. 树的宽度(将进行总共 个递归函数调用 )

在这种情况下，我们的重复关系为T(n) = 2T(n-1).如您所正确指出的，时间复杂度为O(2^n)，但让我们将其与递归树相关联.

Our recurrence relation for this case is T(n) = 2T(n-1). As you correctly noted the time complexity is O(2^n) but let's look at it in relation to our recurrence tree.

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

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

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

This pattern will continue until our base case which will look like the following image:

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

With each successive tree level, our n reduces by 1. Thus our tree will have a depth of n before it reaches the base case. Since each node has 2 branches and we have n total levels, our total number of nodes is 2^n making our time complexity O(2^n).

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

Our memory complexity is determined by the number of return statements because each function call will be stored on the program stack. To generalize, a recursive function's memory complexity is O(recursion depth). As our tree depth suggests, we will have n total return statements and thus the memory complexity is O(n).

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