«Напишите функцию, возвращающую n элементов в последовательности Фибоначчи» - один из наиболее частых вопросов, которые вы можете услышать во время собеседования с задачами кодирования. В этом посте я собираюсь рассмотреть два наиболее типичных решения этой проблемы, а также затронуть ужасную (для большинства начинающих разработчиков) тему временной сложности.

Так что же такое последовательность Фибоначчи? По данным Википедии :

«В математике числа Фибоначчи - это числа в следующей целочисленной последовательности, называемой последовательностью Фибоначчи, и характеризующейся тем, что каждое число после первых двух является суммой из двух предыдущих ».

В зависимости от выбранной начальной точки последовательности (0 или 1) последовательность будет выглядеть так:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

или это:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

ЛЮБОПЫТНЫЙ ФАКТ: последовательность Фибоначчи, также известная как золотое сечение, часто встречается в природе. С помощью этой математической последовательности можно описать такие узоры, как спирали ракушек, кривая волн, семенные головки, сосновые шишки и ветви деревьев. Тот факт, что такие большие, как спирали галактик, и такие маленькие, как молекулы ДНК, следуют правилу золотого сечения, предполагает, что последовательность Фибоначчи является одной из самых фундаментальных характеристик Вселенной.

Хорошо, теперь вернемся к Земле и нашей задаче кодирования последовательности Фибоначчи. Давайте быстро опишем тестовый пример для нашей функции fib (). Если бы мы взяли короткую последовательность Фибоначчи: [0, 1, 1, 2, 3, 5, 8, 13, 21] и fib (4), результат был бы равен 3, поэтому в основном нам нужно вернуть элемент с индексом 4 из нашего массива последовательностей Фибоначчи.

Одно возможное и, вероятно, самое простое решение, которое здесь приходит на ум, - это итерация. Посмотрим, как это будет выглядеть:

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

Обратите внимание, что два первых числа не могут быть эффективно сгенерированы циклом for, потому что наш цикл будет включать сложение двух чисел вместе, поэтому вместо создания пустого массива мы присваиваем нашей переменной arr значение [0, 1], который мы знаем наверняка, всегда будет там. После этого мы создаем цикл, который начинает итерацию с i = 2 и добавляет числа в массив, пока длина массива не станет равной n + 1. Наконец, мы возвращаем число с индексом n массива.

fib(4)
=> 3

Отлично, похоже, это работает. А что, если ваш интервьюер считает, что этого недостаточно, и просит вас реализовать рекурсивное решение?

Хотя рекурсивное решение выглядит довольно простым, его довольно сложно найти, если вы никогда раньше с ним не сталкивались:

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

Итак, в нашем базовом случае возвращается n, если значение меньше 2. Давайте посмотрим на диаграмму, которая поможет вам понять, что здесь происходит с остальной частью нашего кода. Функция fib вызывается с аргументом 5:

В основном наша функция fib будет продолжать рекурсивно вызывать себя, создавая все больше и больше ветвей дерева, пока не достигнет базового случая, из которого она начнет суммировать возвращаемые значения каждой ветви снизу вверх, пока, наконец, не суммирует их все и не вернет целое число равно 5. На то, чтобы погрузиться в происходящее, может потребоваться некоторое время, поэтому посмотрите на дерево и вы поймете, что там происходит.

Для последовательности Фибоначчи настоятельно рекомендуется изучить JavaScript. Теперь, когда мы рассмотрели эти два общих решения проблемы, давайте поговорим о временной сложности.

Некоторые среды тестирования, такие как Jest, например, указывают в миллисекундах, сколько времени потребовалось для выполнения вашей функции. Предполагая, что для этой задачи у нас есть заранее написанные тесты, результаты будут выглядеть так:

Итерационное решение:

Рекурсивное решение:

Теперь посмотрим на случай, когда мы вызываем fib () с n = 15. Итеративное решение заняло 4 мсек, но для выполнения того же действия потребовалось рекурсивное решение 1328 мсек. Это почему?

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

В случае рекурсии решение занимает экспоненциальное время, что можно объяснить тем, что размер дерева экспоненциально растет с увеличением n. Таким образом, с каждым дополнительным элементом в последовательности Фибоначчи мы получаем увеличение количества вызовов функций. Большой O в этом случае равен 2 ^ n.

Надеюсь, теперь, когда вы справились с задачей кодирования последовательности Фибоначчи, у вас повысились шансы на успешное прохождение собеседования. В следующем посте я расскажу о реализации возможного улучшения рекурсивного решения с использованием мемоизации. Будьте на связи!