Python-сообщество

Alexanderrrrrror · Март 14, 2020 22:43:07

Здравствуйте ! Можно ли как-то оптимизировать эту рекурсию и сократить время выполнения кода ?

 def fib_number(n):
	if n==1:
		return 0
	elif n==2:
		return 1
	return fib_number(n-1)+fib_number(n-2)
n= int(input())
print(fib_number(n))

Striver · Март 16, 2020 06:46:07

Можно ли как-то оптимизировать эту рекурсию и сократить время выполнения кода ?

Ну, нормальным подходом будет сделать итеративный алгоритм. Держишь в локальных переменных два последние значения последовательности и проходишь циклом от 1 до n.

Но можно и по-другому.
Если n небольшие, то можно применить так называемую мемоизацию - кешировать результаты твоей функции, тогда она будет для каждого аргумента n вызываться по одному разу. Конечно, при этом будет тратиться много памяти. Как-то так:

 from cachetools.func import lfu_cache
@lfu_cache(maxsize=10000)
def fib_number(n):
	if n==1:
		return 0
	elif n==2:
		return 1
	return fib_number(n-1)+fib_number(n-2)
n= int(input())
print(fib_number(n))

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

Отредактировано Striver (Март 16, 2020 06:49:28)

Python-сообщество

Уведомления

#1 Март 14, 2020 22:43:07

Оптимизация кода.Вывод n- го числа в последовательности Фибоначчи

#2 Март 16, 2020 06:46:07

Оптимизация кода.Вывод n- го числа в последовательности Фибоначчи

Board footer