InterviewCake - забавное место. Этим утром у меня был вопрос, который я уже много раз видел раньше. Напишите функцию, которая вычисляет n-е число Фибоначчи. Давайте разберемся в этой проблеме. Во-первых, что такое число Фибоначчи? Число Фибоначчи - это последовательность чисел, в которой каждое число является суммой двух предыдущих чисел.

Классическая проблема рекурсии, верно? Каков наш базовый случай ... если число равно 0 или 1, вернуть число, иначе рекурсивно вернуть предыдущие суммы. Код выглядит так:

function fib(n){
  if(n === 0 || n === 1){
    return n;
  }
  return fib(n - 2) + fib(n - 1);
}

Однако возникает вопрос, какова временная сложность этого? Моя первая мысль была O (n) правильно, если n было 5, он вычислил fib (5), fib (4), fib (3). Но не будет! Если n было 5, он вычислит fib (4) AND fib (3), затем fib (4) вычислит fib (3) и fib (2), fib (3) вычислит fib (2) и fib (1) . Это определенно не O (N), это бинарное дерево. В двоичном дереве общее количество узлов равно O (2 ^ N), и сортировка не является удобной временной сложностью! Чтобы отсортировать упорядоченное двоичное дерево, мы могли бы выполнять двоичный поиск ... но это другая проблема на другой день. Взгляните на O (2 ^ n), не очень хорошо!

Так как же решить эту проблему за меньшее время? Пора научиться мемоизации!

Мемоизация, определенная в InterviewCake, гарантирует, что функция не запускается для одних и тех же входных данных более одного раза, сохраняя запись результатов для заданных входных данных (обычно в объекте).

Создаем объект, памятку, затем выполняем два шага:

  1. Проверьте памятку, чтобы увидеть, можем ли мы избежать вычисления ответа для любого заданного ввода.
  2. Сохраните результаты любых расчетов в память.
function Fibber(){
  this.memo = {};
}
Fibber.prototype.fib = function(n){
  if(n === 0 || n === 1) {
    return n;
  }
  if(this.memo.hasOwnProperty(n)){
    return this.memo[n];
  }
  this.memo[n] = this.fib(n - 2) + this.fib(n - 1);
  return this.memo[n];
}

Давайте рассмотрим это, где 6 - это вход.

new Fibber().fib(6);
computing fib(6), which is fib(4) + fib(5)
computing fib(4), which is fib(2) + fib(3)
computing fib(2), which is fib(0) + fib(1)
fib(0) + fib(1) is 1
this.memo[2] = 1;
go back up the call stack, but this time we have fib(2) recorded in our hash, so we don’t have to go all the way back down!
computing fib(3), which is fib(1) + fib(2)
fib(1) is 1
we grab memo[2] — 1
this.memo[3] = 2
computing fib(4)
we grab memo[2] — 1, add it to memo[3] — 2
this.memo[4] = 3
fib(5) = memo[3] + memo[4]
fib(5) = 2 + 3
this.memo[5] = 5
fib(6) = memo[4] + memo[5]
fib(6) = 3 + 5
this.memo[6] = 8
return 8

Поскольку ни один узел не вызывается более одного раза, эта стратегия динамического программирования, известная как мемоизация, имеет временную сложность O (N), а не O (2 ^ N). Потрясающие!

Хотя время O (N) хорошее, сложность пространства может быть снижена до O (1). Прямо сейчас с мемоизацией нам нужен объект размером N, можем ли мы сделать это без объекта? Да, мы можем, ввести подход снизу вверх!

Начиная с 1 и 0, первых двух чисел Фибоначчи, устанавливая переменные и изменяя эти два значения, мы создаем самое простое решение! Если наш ввод равен 1 или 0 (или отрицателен), мы возвращаемся соответствующим образом. Если нет, мы устанавливаем переменную twoBehind в 0, переменную oneBehind в 1 и fib, которые мы в конечном итоге вернем, но сможем использовать в наших присвоениях переменных.

Начиная с 1 и пока мы меньше n, мы присваиваем fib значение twoBehind + oneBehind, а затем перемещаем оба значения вверх.

function bottomUpFib(n){
  if(n === 1 || n === 0){
    return n;
  }
  var twoBehind = 0;
  var oneBehind = 0;
  var fib = 0;
  
  for(var i = 1; i < n; i++){
    fib = twoBehind + oneBehind;
    twoBehind = oneBehind;
    oneBehind = fib;
  }
  return fib;
}

Посмотри на этого парня! Снизу вверх!

Напомним, динамическое программирование состоит из трех этапов:

Рекурсия - Big O (2 ^ N)

Воспоминание - O (N) - время, O (N) - пространство

Снизу вверх - O (N) - время, O (1) - пробел