Вычисление чисел Фибоначчи: различия между версиями

Если напрямую написать решение этой задачи, переписав рекурсию в код, то получим экспоненциальное время выполнения, ведущее себя примерно как <math> \Phi^n </math>, где <math> \Phi </math> — [[w:золотое сечение|золотое сечение]].

В данном случае организовать запоминание перекрывающихся подзадач очень легко — заведем массив dp, dp[i] будет значением <math> F_i </math>. В этой задаче легко организовать восходящее [[w:Динамическое программирование|ДП]], так как мы знаем, что для вычисления <math>F_n</math> понадобятся <math>F_{n-1}</math> и <math>F_{n-2}</math>. Асимптотическая сложность алгоритма будет [[w:O-большое|O]](n) время и O(n) памяти.(Требуется массив и один проход по массиву).