¿Cuál es la complejidad temporal de Fibonacci con memoización fib(n)?
Opciones
- O(2ⁿ)
- O(n) (Opción correcta)
- O(log n)
- O(n²)
Respuesta
O(n)
Por qué
El fib recursivo ingenuo llama a fib(n-1) y fib(n-2), que llaman a los mismos valores una y otra vez: unas 2ⁿ llamadas.
Con memoización, cada fib(k) se calcula una vez y luego se lee de una caché. Solo hay n valores distintos, así que O(n).
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)Recuerda
La memoización convierte trabajo repetido en trabajo de una sola vez.