如何解釋緩存的斐波那契算法的複雜性

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); 

將溶液從「開裂編碼訪談」取出並適於的JavaScript。 所以這裏的功能「不是很好」樹叫

我在想這樣的：「最左邊的分支（大膽的）就是評估正在發生的事情」，這絕對是是編號首次傳遞給allFib函數。所以複雜度是O（n）。右邊的所有內容都將從緩存中取出，並且不需要額外的函數調用「是否正確？還有如何將其與樹」理論「連接起來。在這種情況下，樹的深度和高度是4不是5（接近N但不是它）。我想答案是不直觀，但更可靠。

Answer 1

首先，檢查陰性n，和值移動到零。

那麼，如果一個值檢查如果不是，則將該值分配給緩存並返回結果

對於n === 0或n === 1的特殊情況分配n。

function fibonacci(number) { 
 
    function f(n) { 
 
     return n in cache ? 
 
      cache[n] : 
 
      cache[n] = n === 0 || n === 1 ? n : f(n - 1) + f(n - 2); 
 
    } 
 

 
    var cache = []; 
 
    return f(number); 
 
} 
 

 
console.log(fibonacci(15)); 
 
console.log(fibonacci(5));

與預定義的值在cache部分中，如建議Thomas。

function fibonacci(number) { 
 
    function f(n) { 
 
     return n in cache ? 
 
      cache[n] : 
 
      cache[n] = f(n - 1) + f(n - 2); 
 
    } 
 

 
    var cache = [0, 1]; 
 
    return f(number); 
 
} 
 

 
console.log(fibonacci(15)); 
 
console.log(fibonacci(5));

Answer 2

這裏是真正使用高速緩存功能：

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是備註的最後一項。

由此可以知道與=的示例中，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)。箭頭顯示所做的呼叫。越靠左，遞歸越深。當相應的結果被存儲在備忘錄氣泡被着色：

這顯然是O（n）的時我是給定的恆定。