Программа рекурсии находит N-е число Фибоначчи с течением времени T. За какое время эта программа найдет N + 1 число, N + 2, 2N?
Есть программа нахождения n-нного числа Фибоначчи:
def fibonacci(a):
if a != 0 and a != 1:
return fibonacci(a - 1) + fibonacci(a - 2)
else:
return a
n = int(input())
print(fibonacci(n))
Найти время для N + 1, N + 2, 2N
Ответы (2 шт):
Дам вырезку отсюда
Выражаясь грубым языком O-нотации, такое решение имеет временную сложность O(e^n). То есть — время выполнения этой функции растёт экспоненциально при увеличении n. То есть — когда n увеличивается на, время выполнения увеличивается в. Грубо говоря, если fib(45) вам пришлось ждать час, то fib(46) вы будете ждать два часа, fib(47) — 4 часа, и так далее. Я разжёвываю так подробно, чтобы каждый читатель, даже верстальщик, впервые попробовавший свои силы в написании скриптов, мог осознать ужас ситуации.
Можно получить более точную оценку числа вызов функции ~(1+sqrt(5)) fib(n)
Формула числа вызовов рекурсивной функции для расчёта чисел Фибоначчи:
G(N) = 2*F(N) - 1
Где:
G(N)- число вызовов функции при расчёте N-го числа ФибоначчиF(N)- N-е число Фибоначчи.