Алгоритмы JavaScript: решение последовательности Фибоначчи (LeetCode)

Числа Фибоначчи , обычно обозначаемые как числа, F(n)образуют последовательность, называемую последовательностью Фибоначчи , так что каждое число является суммой двух предыдущих, начиная с 0и 1. Числа в следующей целочисленной последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ……..

Это

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Пример 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

• 0 <= n <= 30

Есть несколько вариантов решения этой проблемы: Рекурсивный подход.

Рекурсивный подход

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

Динамическое программирование с использованием мемоизации (подход «сверху вниз»)

Мы можем избежать повторяющейся работы, выполняемой в рекурсивном режиме, сохраняя рассчитанные до сих пор числа Фибоначчи. Нам просто нужно сохранить все значения на карте. Временная сложность : O(N) и пространственная сложность : O(N) .

Итерационный подход

Итерация с решением всех подзадач и возвратом ответа для элемента N с использованием уже вычисленных значений Фибоначчи. Временная сложность : O(N) и пространственная сложность : O(N) .

Итерационный подход ( оптимизированное пространство)

Мы можем оптимизировать итерационный подход, сохраняя два предыдущих числа только потому, что это все, что нам нужно, чтобы получить следующее число Фибоначчи в последовательности. Временная сложность : O(N) и пространственная сложность : O(1) .

Подход матричного возведения в степень

Используйте возведение в степень матрицы, чтобы получить число Фибоначчи из элемента в (0, 0) в результирующей матрице. Чтобы сделать это, мы можем полагаться на матричное уравнение для последовательности Фибоначчи, чтобы найти N-е число Фибоначчи:

Как работает эта формула вы можете посмотреть в Wiki

Это решение имеет: временную сложность : O(logN) и пространственную сложность : O(logN) .

Математический подход

Мы можем использовать golden ratio forumula:

Вот ссылка , чтобы узнать больше о том, как работают последовательность Фибоначчи и золотое сечение.

Это решение имеет: временную сложность : O(logN) и пространственную сложность : O(1) .

Также иногда требуется вернуть не значение для заданного N, а вернуть массив элементов Фибоначчи вплоть до заданного N.

Пример:

Input: n = 7
Output: [0, 1, 1, 2, 3, 5, 8, 13]

и динамическое программирование с использованием запоминания с небольшими изменениями:

Мы рассмотрели разные варианты решения задачи Фибоначчи, самый сложный для понимания — Матричное возведение в степень, но обычно для собеседования достаточно знания 4-х предыдущих методов.

Надеюсь, это было полезно для вас!

Спасибо за прочтение! Увидимся.

Больше контента на PlainEnglish.io . Подпишитесь на нашу бесплатную еженедельную рассылку . Следите за нами в Twitter , LinkedIn , YouTube и Discord . Заинтересованы в хакинге роста? Проверьте Цепь .