java - 内存斐波那契码的空间复杂度

Question

void allFib(int n) {
   int[] memo = new int[n + 1];
   for(int i = 0; i < n; i++){
      System.out.println(i + ": "+ fib(i, memo));
   }
}

int fib(int n, int[] memo) {
   if (n <= 0) return 0;
   else if (n == 1) return 1;
   else if (memo[n] > 0) return memo[n];
   memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
   return memo[n];
}

在上面打印前 n 个斐波那契数的内存代码中，由于 fib 方法中的递归调用，空间复杂度是多少 (memo[n]= fib(n - 1, memo) + fib( n - 2，备忘录)；)？尽管它们看起来像递归调用，但它们实际上所做的只是查找 memo[n - 1] 和 memo[n - 2]，因为它们保证已经被计算过。但是因为它们采用这种形式并在内存中建立自己的堆栈，所以每个调用都应该有内存占用吗？如果是这样，什么？

如果我将该行替换为 memo[n] = memo[n - 1] + memo[n - 2]，则该行贡献的空间复杂度将减少到 O( 1)对吗？

我知道，由于 memo 数组的大小为 n + 1，因此整体空间复杂度至少为 O(n)。

Answer 1

当您计算从最小到最大的连续斐波那契数时，即使使用递归调用，额外的空间复杂度也是O(1)。

事实上，循环中对 fib 的每次新调用都会产生两次调用(除了 i = 0 和 i = 1 >，其中不进行额外的调用)。 每次调用都需要恒定的空间量。递归深度以 2 为界，因此所需的额外空间总量是恒定的。

如果将其替换为带有求和的循环 memo[n] = memo[n - 1] + memo[n - 2]，额外的空间复杂度将保持 O(1 )，因此不会减少。