¿Hasta qué punto se puede optimizar un programa para calcular la secuencia de Fibonacci?

Introducción

Cuando estaba aprendiendo Python, nuestro maestro nos dio una tarea: calcular el enésimo número de la secuencia de Fibonacci.

Creo que es muy fácil, así que escribo este código:

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

Más tarde, sé que este tipo de solución cuesta demasiado tiempo.

Optimizar un programa

Cambio la solución a iteración.

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

    return ls[n-1]

Utilizo matplotlib para dibujar el tiempo que me costó:

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()

Resultado aquí:

El tiempo que costó es muy corto.

Pero escribo mentira (300000), cuesta 5,719049899998936 segundos. Es muy largo.

Cuando sea mayor, aprendo CACHE, así que cambio la solución para usar dict para almacenar el resultado.

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



O podemos escribir el CACHE nosotros mismos.


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