Наверное…
Все мы знаем знаменитую последовательность Фибоначчи, т.е.
0 1 1 2 3 5 8 13 21 34 55 ...
где каждый член просто равен сумме двух предыдущих членов. Все просто, правда? Это также широко используемый метод обучения рекурсии в любом руководстве по языку программирования. Алгоритм, изложенный в этих руководствах, всегда ужасен:
Но как это вообще ужасно ?! Это так просто и просто!
Это может быть просто, но это не хорошо. Позвольте мне показать вам, как это сделать. Из-за рекурсии в этом алгоритме многие вычисления повторяются. Если вы посмотрите на это дерево, представляющее рекурсивные вызовы функций, вы можете ясно увидеть одни и те же вызовы функций несколько раз. Это неприемлемо. Это приводит к увеличению времени вычислений и нерациональному использованию ресурсов.
Временная сложность этого наивного алгоритма оказывается равной 2 ^ n. Глядя на график ниже, сравнивающий различные временные сложности Big-O, мы можем сделать вывод, что этот алгоритм явно бесполезен для больших чисел.
"Это круто и все такое, что вы можете с этим поделать?"
Просто остановим повторяющиеся вызовы функций. Один из способов сделать это - запоминание. Вы спросите, что это?
В вычислениях мемоизация или мемоизация - это метод оптимизации, используемый в основном для ускорения компьютерных программ за счет сохранения результатов дорогостоящих вызовов функций и возврата кэшированного результата, когда те же входные данные повторяются снова. .
По сути, мы сохраним предыдущие члены последовательности Фибоначчи, чтобы вычислить дальнейшие члены. Мы можем сделать это с помощью простого массива. Вот простой код Python для этого:
Временная сложность для этого алгоритма оказывается O (n), что довольно хорошо, учитывая, насколько плох был предыдущий. Одна из проблем заключается в том, что вам нужна дополнительная память для хранения терминов в массиве. Я призываю вас найти решение для этого.
Можете ли вы также найти алгоритм для генерации последовательности Фибоначчи с использованием матричного возведения в степень?
