Насколько можно оптимизировать программу для вычисления последовательности Фибоначчи?

Введение

Когда я изучал Python, наш учитель дал нам домашнее задание — вычислить N-е число последовательности Фибоначчи.

Я думаю, что это очень просто, поэтому я пишу такой код:

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

Позже я понимаю, что такое решение требует слишком много времени.

Оптимизация программы

Я меняю решение на итерацию.

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

Я использую matplotlib, рисую время, которое это стоило:

import time
import matplotlib.pyplot as plt


def bench_mark(func, *args):
    # calculate the time
    start = time.perf_counter()
    result = func(*args)
    end = time.perf_counter()

    return end - start, result  # return the time and the result

def fib(n):
    ls = [1,1]
    for i in range(2,n):
        ls.append(ls[i-1] ls[i-2])

    return ls[n-1]

mark_list = []

for i in range(1,10000):
    mark = bench_mark(fib,i)
    mark_list.append(mark[0])
    print(f"size : {i} , time : {mark[0]}")

plt.plot(range(1, 10000), mark_list)
plt.xlabel('Input Size')
plt.ylabel('Execution Time (seconds)')
plt.title('Test fot fibonacci')
plt.grid(True)
plt.show()

Результат здесь:

Времени, которое это стоило, очень мало.

Но я пишу fib(300000), стоимость 5.719049899998936 секунд. Слишком длинное.

Когда я вырасту, я выучу КЭШ, поэтому я меняю решение на использование dict для хранения результата.

from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
    if n 



Или мы можем написать КЭШ самостоятельно.



def fib(n, cache={}):
    if n in cache:
        return cache[n]
    elif n