Алгоритм последовательности Фибоначчи

Чтобы начать последовательность Фибоначчи, это последовательность чисел, начинающаяся с 0 и 1, затем каждое число после этого получается путем сложения двух предыдущих чисел. Эта последовательность чисел бесконечна, но вот первые 10 чисел последовательности для примера:

0,1,1,2,3,5,8,13,21,34......

Исходя из этого, то, что нам нужно решить или что нас могут попросить решить на собеседовании по кодированию, - это написать функцию, которая возвращает вам n-е число в последовательности Фибоначчи. Большинство из этих проблем алгоритмов, с которыми вы могли столкнуться на собеседовании по кодированию, были решены несколькими способами, одни более эффективно, чем другие.

Для этого примера я напишу в JavaScript два способа решения этой проблемы: базовое итеративное решение с циклом for и рекурсивное решение. Во-первых, ниже приведен код итеративного решения:

function fibonacci(n){
  let fibArray = [0,1]
  for (let i=2; i < n + 1; i++) {
    fibArray.push(fibArray[i-2] + fibArray[i-1])
  }
  return fibArray[n]
}

Начнем с создания массива и помещения в него первых двух чисел. Затем, используя цикл for, мы добавляем предыдущее число и число два перед текущей точкой в ​​массиве и помещаем эту сумму в конец массива. Этот цикл продолжается до тех пор, пока вход n + 1 не станет равным i, которое начинается с 2. Затем наш оператор return берет из созданного нами массива n-е число. Это работает и не является плохим решением, поскольку его временная сложность Big O равна O (n), поскольку он проходит через цикл for.

Следующее решение с использованием рекурсии - хороший пример, чтобы увидеть, как работает рекурсия, или изучить рекурсию. Ниже приведен код рекурсивного решения:

function fibonacci(n) {
  if (n < 2) {
    return n
  }
  return fibonacci(n-1) + fibonacci(n-2)
}

Код этого решения кажется коротким и простым. Однако это не очень практично, так как имеет временную сложность Big O, равную O (2 ^ n), что плохо и не то, чего вы хотите достичь. С увеличением n временная сложность растет экспоненциально из-за экспоненциального увеличения количества вызовов функций. Для каждого числа n больше 2 мы делаем еще два вызова функций.

Курс Udemy Учебный курс с собеседованием по кодированию: алгоритмы + структуры данных предлагает несколько решений этой проблемы.