Решите его рекурсивно, запоминать и итеративно
Возможно, вы слышали о последовательности Фибоначчи как о «золотом сечении». Это название связано с соотношением чисел 1,618034.
Говорят, что это выражается в природе, когда мы смотрим на такие вещи, как точки роста деревьев или лепестки цветов, или части нашего тела (один нос, два глаза, пять пальцев на руке).
Я не буду обсуждать теорию Фибоначчи, а буду обсуждать два с половиной способа ее решения с помощью функций JavaScript.
Что такое последовательность Фибоначчи?
Последовательность Фибоначчи, названная в честь итальянского математика Леонардо Пизанского, представляет собой последовательность чисел, в которой каждое число после первых двух чисел является суммой исходящих чисел. Давайте посмотрим ниже.
Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89... Such that: 1 + 1 = 2; 2 + 3 = 5; 3 + 5 = 8; 8 + 13 = 21; 13 + 21 = 34; 21 + 34 = 55; 34 + 55 = 89; and so on to infinity
Мы можем рассматривать числа как древовидную структуру данных. Если мы структурируем последовательность в виде дерева, мы сможем вычислить значение Фибоначчи любого числа в этой позиции.
Начиная снизу и продвигаясь вверх, мы можем добавить дочерние пары и перейти к fib(5), где на самом деле значение равно 5. Мы видим, что fib(1), fib(2), fib(3) повторяются несколько раз.
Один из подходов к решению этой последовательности - динамическое программирование. Мы можем разбить проблему на более мелкие части, ища повторения.
Некоторые способы решения этой проблемы заключаются в использовании рекурсии, мемоизации или итерации. У каждого из них есть свои временные сложности, как мы увидим. Давайте займемся этим и напишем функции Фибоначчи с помощью JavaScript.
Наивное решение - O (2 ^ n)
Если fib(1) = 1 и fib(2) = 1, то мы можем вычислить fib(n) = fib(n-1) + fib(n-2). Следовательно, мы можем написать решение с использованием рекурсии следующим образом:
function fibRecursion(n) {
if(n <= 2) return 1;
return fib(n-1) + fib(n-2);
}
Функция принимает целое число n. В строке 1 у нас есть базовый случай, так что целое число n, меньшее или равное 2, даст нам начальное число 1, поскольку мы хотим начать отсчет с третьего числа.
Затем в последней строке мы рекурсивно вызываем функцию. Это решение считается наивным, потому что, хотя оно и выполняет свою работу, оно не является оптимальным. Временная сложность этой функции O (2 ^ n) очень медленная.
Если мы вернемся к дереву, это решение заставит нас снова и снова перебирать каждого дочернего элемента, даже если мы уже вычислили значение.
В случае fib(5) не совсем понятно, как эта функция будет работать медленно, но когда мы начнем использовать большие входные значения, дерево будет быстро расти, и его выполнение станет очень дорогостоящим.
Давайте посмотрим на лучшее решение, все еще использующее рекурсию.
Рекурсивное и мемоизированное решение - O (n)
Одна проблема с наивным решением заключается в том, что существует много дубликатов вызовов функций. Один из способов оптимизировать это - запомнить рассчитанные ранее значения и сохранить их. Эта концепция известна как мемоизация.
Мемоизация - это метод оптимизации, который позволяет сократить время выполнения за счет сохранения результатов при повторении одного и того же ввода. Мы можем хранить или запоминать данные в такой структуре данных, как массив или объект.
Итак, давайте сделаем это и сохраним вычисленные значения в массиве. На этот раз наша функция примет два аргумента: n и memo=[].
У нас снова есть базовый случай в строке 2. В строке 1 мы говорим, что если наш мемо-массив с индексом n не является неопределенным, мы хотим вернуть значение.
Var res назначается рекурсивный вызов функции. Затем memo[n] будет присвоено значение res. В конечном итоге функция вернет целое число последовательности в позиции n.
Это решение оказывается намного быстрее, чем наивное решение, потому что по мере роста n увеличивается время, необходимое для выполнения. Следовательно, это рекурсивное и мемоизированное решение имеет большую временную сложность O (n).
Не так уж и велика космическая сложность. Мемоизация занимает много места по мере роста n, поэтому пространственная сложность этого решения также равна O (n).
Это решение следует нисходящему подходу , начиная с корня дерева и продвигаясь вниз к дочерним элементам.
Итерационное решение: табуляция A.K.A. «Снизу вверх» - O (n)
Я упомянул акцент на двух с половиной решениях, а не на трех, поскольку мемоизированное решение включает рекурсию.
Давайте посмотрим на другой подход к решению Фибоначчи с итерацией. Как вы, возможно, знаете, итерация включает повторение цикла снова и снова, пока не будет выполнено какое-либо условие. Как и мемоизация, мы будем хранить значения каждой позиции, но вместо «памятки» мы будем использовать «таблицу».
В нашем случае «таблица» также является структурой данных, такой как массив или объект. Этот итеративный подход известен как табуляция. Табуляция имеет лучшую пространственную сложность , чем мемоизация на O (1), однако временная сложность большого O по-прежнему составляет O (n).
Давайте посмотрим на функцию:
У нас снова есть базовый случай в строке 1. В строке 2 мы устанавливаем нашу «таблицу», которая представляет собой массив из первых двух чисел. Поскольку мы начинаем с индекса 1, для индекса 0 может быть установлено значение 0 или неопределенное значение.
Затем мы начинаем цикл с индекса 3, пока не достигнем n. Наконец, мы просто возвращаем значение индекса nth. Вот и все! Мы только начинаем с «низа» таблицы и поднимаемся вверх.
Заключение
Лично я считаю, что итерацию легче понять по своей сути. На первый взгляд, код намного проще, чем рекурсия.
В нашем случае с последовательностью Фибоначчи итерация кажется правильным решением, если мы оптимизируем с учетом временных и пространственных сложностей.
Рекурсия, мемоизация и табуляция / итерация - все это части динамического программирования. Вот несколько ресурсов, которые вы можете найти, чтобы узнать больше! Удачного кодирования.
