javascript - 如何解释缓存的斐波那契算法的复杂性

Question

我正在尝试解释正确缓存的斐波那契算法的复杂性。这是代码(https://jsfiddle.net/msthhbgy/2/):

function allFib(n) {
  var memo = [];
  for (var i = 0; i < n; i++) {
    console.log(i + ":" + fib(i, memo))
  }
}

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

allFib(5);

解决方案取自“Cracking the coding interview”并适配javascript。所以这是一个“不太好”的函数调用树

我是这样想的:“最左边的分支(粗体)是计算发生的地方”，它肯定是第一次传递给 allFib 函数的数字。所以复杂度是O(n)。右边的所有内容都将从缓存中获取，不需要额外的函数调用。是否正确？还有如何将其与树“理论”联系起来。在这种情况下，树的深度和高度为 4，但是不是 5(接近 n 但不是它)。我希望答案不直观但更可靠。

Answer 1

这是一个真正使用缓存的函数:

function Fibonacci() {
  var memo = [0, 1];

  this.callCount = 0;

  this.calc = function(n) {
    this.callCount++;
    return n <= 0 ? 0 
         : memo[n] || (memo[n] = this.calc(n - 1) + this.calc(n - 2));
  }
}

var fib = new Fibonacci();

console.log('15! = ', fib.calc(15));
console.log('calls made: ', fib.callCount);
fib.callCount = 0; // reset counter
console.log('5! = ', fib.calc(5));
console.log('calls made: ', fib.callCount);
fib.callCount = 0;
console.log('18! = ', fib.calc(18));
console.log('calls made: ', fib.callCount);

函数调用次数为:

(n - min(i,n))*2+1

i 是memo 中的最后一个条目。

你可以通过 n = 18 和 i = 15 的例子看到:

调用按以下顺序进行:

calc(18)
calc(17)   // this.calc(n-1) with n=18
calc(16)   // this.calc(n-1) with n=17
calc(15)   // this.calc(n-1) with n=16, this can be returned from memo
calc(14)   // this.calc(n-2) with n=16, this can be returned from memo
calc(15)   // this.calc(n-2) with n=17, this can be returned from memo
calc(16)   // this.calc(n-2) with n=18, this can be returned from memo

一般模式是 this.calc(n-1) 和 this.calc(n-2) 被调用的次数一样多(当然) ，加上原始调用 calc(n)。

这是您第一次调用 fib.calc fib.calc(5) 时的动画。箭头显示发出的调用。越往左，递归越深。当相应的结果存储在 memo 中时，气泡会变色:

当 i 是给定常数时，这显然是 O(n)。