Сложность рекурсивного алгоритма Фибоначчи

Используя следующий рекурсивный алгоритм Фибоначчи:

def fib(n):
   if n==0:
      return 0
   elif n==1
      return 1
   return (fib(n-1)+fib(n-2))

Если я введу число 5, чтобы найти fib (5), я знаю, что это выведет 5, но как мне проверить сложность этого алгоритма? Как рассчитать соответствующие шаги?

В большинстве случаев вы можете представлять рекурсивные алгоритмы, используя рекурсивные уравнения. В этом случае рекурсивное уравнение для этого алгоритма имеет вид . Затем вы можете найти замкнутую форму уравнения, используя метод подстановки или метод разложения (или любой другой метод, используемый для решения повторений). В этом случае вы получите T ( n ) = Θ ( ϕ n ) , где $T(n) = T(n-1) + T(n-2) + \Theta(1)$$T(n) = \Theta(\phi^n)$$\phi$это золотое сечение ( )$\phi = \frac{(1 + \sqrt{5})}{2}$

Если вы хотите узнать больше о том, как решать повторения, я настоятельно рекомендую вам прочитать главу 4 « Введение в алгоритмы» .

в качестве альтернативы рекуррентным отношениям / математическому анализу (но не замене ) простое эмпирическое упражнение, которое, по-видимому, не преподается очень часто на уроках, но очень информативно, состоит в подсчете количества выполнений функции, а затем на графике подсчета для диапазона малых п входов, а затем кривой соответствуют результату. результаты будут в целом близко соответствовать теоретическому математическому подходу.

Хороший вспомогательный материал для этого упражнения можно найти в бесплатной онлайн главе 3 « Время выполнения алгоритмов / Основы информатики» , Уллман.

Результатом fib (n) является сумма всех рекурсивных вызовов, которые вернули 1. Следовательно, существует ровно fib (n) рекурсивных вызовов, оценивающих fib (1). Таким образом, время выполнения Ω (fib (n)); вам нужно показать, что вызовы, возвращающие 0, и другие рекурсивные вызовы не вносят существенных изменений в это.

То же самое относится к любой рекурсивно определенной функции, которая либо возвращает 1, либо 0, либо результат другого рекурсивного вызова.

$T(n)=T(n-1)+T(n-2)$ $T(n)>2T(n-2)$$T(n-1)>T(n-2)$$T(n)= \Omega(c^{n})$