Я изучаю динамическое программирование, и хорошее место для начала - последовательность Фибоначчи. Сама последовательность часто используется в качестве введения в рекурсию в программировании из-за ее простоты и знакомости математикам.
Это предназначено для обеспечения ясности как динамического программирования, так и его реализации в Swift.
Последовательность Фибоначчи представляет собой последовательность двух предшествующих ей чисел, которая, как говорят, определяет размеры всего, от Великой пирамиды в Гизе до морских ракушек. Правильно, это одна из тех математических последовательностей, которые, кажется, появляются повсюду (в том числе в природе) и связаны с золотым сечением (излюбленное число дизайнеров во всем мире, поскольку, как говорят, это фактор, который делает Мона Лизу красивой) .
Последовательность начинается с этих нескольких первых чисел:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34…
Переход к следующему числу в последовательности 55 (в результате двух предыдущих чисел в последовательности 21 + 34)
Итерационный подход
Он проходит мой самый базовый набор тестов BasicTestSuite.playground, который проверяет, соответствует ли результат приведенной выше последовательности.
По сути, алгоритму нужно передать первые два числа последовательности:
f(0) = 0 f(1) = 1
что эквивалентно нашему закодированному
var a = 0 var b = 1
затем мы вычисляем каждый последующий элемент последовательности (каждый элемент является суммой двух предыдущих элементов в соответствии с последовательностью Фибоначчи).
Первые два элемента уже определены (в первом проходе как 0 и 1), поэтому результатом будет сложение двух предыдущих чисел. Мы зацикливаемся, то есть нам нужно сохранить ссылку на предыдущий номер, кроме одного.
Рекурсивный подход
Поскольку каждый элемент последовательности Фибоначчи состоит из двух предыдущих элементов последовательности, это идеальный кандидат для рекурсивной стратегии.
Еще раз нам нужно знать первые два элемента последовательности, и мы думаем об этом как о базовых случаях, здесь представленных оператором защиты в приведенном ниже коде (который доставит fib [0] = 0 и fib [1] = 1, что действительно является первыми двумя элементами последовательности).
Время O (2 ^ n), Пространство O (n)
Мы можем видеть это, проиллюстрированное деревом, показанным ниже:
чтобы вычислить 4-й элемент в последовательности, нам нужно знать fib (3), fib (2) и fib (1).
Мы делаем это рекурсивно через строку:
return fib(n - 1) + fib(n - 2)
поскольку каждый элемент последовательности (n) определяется двумя предшествующими ему.
Другими словами:
f(4) = f(3) + f(2) = f(2) + f(1) = f(1) + f(0) + f(1)
Однако мы видим недостаток этого метода: дерево показывает, что мы вычисляем fib (2) и fib (1) несколько раз. Когда мы делаем больше работы, чем это абсолютно необходимо, мы часто можем оптимизировать наш код, чтобы он работал лучше.
В этом случае мы можем минимизировать работу, используя динамическое программирование.
Нисходящее динамическое программирование (запоминание)
В Swift самый простой способ улучшить наш рекурсивный подход - это запоминание.
Время O (n), пространство O (n)
По сути, это тот же алгоритм, но с кешем, чтобы не приходилось пересчитывать уже вычисленные значения. С помощью Swift можно передать кеш из экземпляра функции. Для этого используются некоторые более продвинутые функции Swift, но они включены здесь для полноты картины.
Время O (n), пространство O (n) [без изменений, приведенных выше]
Снизу вверх динамическое программирование
Снизу вверх, пожалуй, лучше всего думать как о начале с самого начала и, следовательно, без рекурсии.
Подходы снизу вверх обычно позволяют избежать проблемы рекурсии, когда стек вызовов может быть построен до такого уровня, что мы видим печально известное переполнение стека (и кажется, что Swift не гарантирует хвостовую рекурсию, поэтому у нас нет легкого выхода. ).
Решение Фибоначчи будет выглядеть следующим образом:
Время O (n), пространство O (n)
Но есть еще одна оптимизация, которую мы можем сделать, поскольку мы смотрим на эту сложность пространства и думаем ... мы можем сделать немного лучше.
Для последовательности Фибоначчи нам нужны только два предыдущих значения, но в приведенном выше решении у нас есть массив размера n. Конечно, мы можем просто сохранить два предыдущих значения, пока идем по последовательности Фибоначчи? Оказывается, мы можем, и пример решения приведен ниже:
Время O (n), Пространство O (1)
Я надеюсь, что это немного помогло, хотя эти идеи немного доступны в Интернете, может быть сложно найти ресурсы Swift, поэтому я надеюсь, что это было полезно. Если да, возможно, вы захотите «хлопнуть меня в ладоши» или оставить комментарий ниже.
Спасибо
