— — Направления
Выведите n-ю запись ряда Фибоначчи.
Ряд Фибоначчи — это порядок чисел, в котором
каждое число является суммой двух предыдущих.
Например, последовательность
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
формирует первые десять элементов ряда Фибоначчи.
Пример:
выдумка(4) === 3
Во-первых, давайте взглянем на итеративное решение этой проблемы.
Если бы мы просто вернули результат и вызвали нашу функцию fib(4), вывод на консоль выглядел бы так.
Но нам нужно конкретное число в последовательности, поэтому…
Вот и все для итеративного решения. Сложность времени выполнения для этого решения равна O(n) или линейна — это означает, что по мере того, как входное число увеличивается на единицу, увеличивается и объем работы, которую мы должны выполнить в алгоритме.
Вот рекурсивное решение. Сложность выполнения этого решения равна O(2^n) или экспоненциальна, а это означает, что если число, которое мы передаем в fib(n), увеличивается на 1, объем работы, который должен быть выполнен внутри функции, удваивается (или в этом случае, почти вдвое). Это худший сценарий. Скорее всего, на собеседовании вас спросят, как можно ускорить этот алгоритм. Ответ… Мемоизация.
У меня нет времени вдаваться в полноценную дискуссию о мемоизации здесь, но просто чтобы вы знали, что происходит, мы создаем этот объект кеша и сохраняем числа, с которыми вызывается fib(n), как ключи, а также результаты как значения, чтобы не делать ненужных вызовов fib(n). Это резко снижает сложность рекурсивного решения во время выполнения до O(n) или линейного времени.
