Как объяснить сложность алгоритма сложенного алгоритма фибоначчи

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 (рядом с п, но не это). Я хочу, чтобы ответ не интуитивно, но более надежным.

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 - последняя запись в памятка.

Это можно увидеть следующим образом на примере п = 18 и я = 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). Стрелки показывают вызовы, которые сделаны. Чем больше слева, тем глубже рекурсия. Пузырьки окрашены, когда соответствующий результат сохраняется в записке:

Это, очевидно, является О (п), когда я является заданной константой.