Fibonacci Number

Q: ¿Cuál es la complejidad temporal de la función recursiva de Fibonacci?

La recursión ingenua realiza 2 × F(n+1) - 1 llamadas, una cantidad que crece como 1.618^n y suele escribirse O(2^n) . Para n = 45 , son aproximadamente 3.7 × 10^9 llamadas. Almacenar cada resultado una sola vez, en una tabla o en dos variables, reduce la complejidad a O(n) .

Q: ¿Cómo se resuelve Fibonacci con programación dinámica?

Comienza con la recurrencia F(n) = F(n-1) + F(n-2) y calcula los valores en orden creciente de n , almacenando cada uno. Puedes rellenar una tabla de abajo hacia arriba o conservar la función recursiva y almacenar en caché sus resultados, lo que se denomina memorización. De cualquier manera, cada valor se calcula una sola vez, así que el trabajo total es O(n) .

Q: ¿Se puede calcular Fibonacci en espacio O(1)?

Sí. Cada número depende solo de los dos anteriores, así que bastan dos variables. Conserva los dos últimos valores y avánzalos en cada paso. Eso requiere un tiempo de O(n) y un espacio adicional de O(1) .

Q: ¿Hay una forma más rápida que O(n)?

Sí. La matriz [[1, 1], [1, 0]] elevada a la potencia n contiene F(n) en su esquina superior derecha, y la potenciación por cuadrados repetidos calcula esa potencia con O(log n) multiplicaciones de matrices. También existe una fórmula cerrada con potencias de la proporción áurea, pero funciona con números de punto flotante y pierde precisión a medida que crece n , por lo que se prefieren los métodos con enteros.

PrincipianteProgramación dinámica Recursión

+10

Los números de Fibonacci comienzan con F(0) = 0 y F(1) = 1, y cada número posterior es la suma de los dos anteriores: F(n) = F(n-1) + F(n-2). La secuencia comienza así: 0, 1, 1, 2, 3, 5, 8, 13. Tu función recibe n y devuelve F(n).

Función

fib(n: integer) → integer

ninteger: la posición en la secuencia de Fibonacci, contando desde 0
Devuelveinteger: el número de Fibonacci F(n)

Restricciones

0 ≤ n ≤ 45
La respuesta cabe en un entero con signo de 32 bits: F(45) = 1134903170.

Ejemplos

Entrada: n = 4
Salida: 3
Explicación: Cuenta hacia arriba desde el inicio: F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2 y F(4) = 2 + 1 = 3.

Entrada: n = 10
Salida: 55
Explicación: La secuencia desde el índice 0 es 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. El número en el índice 10 es 34 + 21 = 55.

+13 pruebas ocultas al enviar

Para ir más allá

¿Puedes calcular F(n) en tiempo O(log n)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

La definición ya es una función recursiva, y escribirla así da la respuesta correcta. La trampa está en el tiempo de ejecución: las dos llamadas recursivas repiten el trabajo de la otra, y el número de llamadas crece exponencialmente con n. La programación dinámica lo soluciona calculando cada número de Fibonacci una sola vez, de abajo hacia arriba. El último paso conserva solo los dos números que necesita el siguiente.

Recursión directamente desde la definición

Correcto, pero no termina con las pruebas más grandes

Intuición

Traduce la definición palabra por palabra. fib(0) es 0, fib(1) es 1 y cualquier valor mayor devuelve fib(n-1) + fib(n-2). Cada cadena de llamadas termina en uno de los dos casos base, así que la respuesta es correcta.

Ahora cuenta las llamadas. fib(5) llama a fib(4) y fib(3), pero fib(4) vuelve a llamar a fib(3). Al final, fib(3) se ejecuta dos veces, fib(2) tres veces y fib(1) cinco veces, y fib(5) hace 15 llamadas en total. Se vuelven a calcular los mismos valores una y otra vez.

El número de llamadas sigue los propios números de Fibonacci: calcular F(n) hace 2 × F(n+1) - 1 llamadas. Para n = 45, eso equivale a unas 3.7 × 10^9 llamadas, demasiadas para un límite de tiempo. El límite suele escribirse O(2^n); el crecimiento exacto es de alrededor de 1.618^n. La recursión tiene solo n niveles de profundidad, así que la pila necesita O(n) espacio.

Algoritmo

Si n es 0 o 1, devuelve n.
De lo contrario, llama a la función con n-1 y con n-2.
Devuelve la suma de los dos resultados.

def fib(n):
    if n < 2:
        return n  # F(0) = 0, F(1) = 1
    return fib(n - 1) + fib(n - 2)

Rellena una tabla desde abajo hacia arriba

Intuición

La recursión es lenta solo porque olvida. Si escribes cada número de Fibonacci la primera vez que lo calculas, cada uno requiere una sola suma. Crea una tabla f con posiciones para los índices de 0 a n, establece f[0] = 0 y f[1] = 1, y completa el resto de izquierda a derecha con f[i] = f[i-1] + f[i-2].

El orden de izquierda a derecha es lo que hace que funcione: cuando llegas a f[i], ambos números que necesita ya están en la tabla. Para n = 10, la tabla se completa así: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, y la respuesta es el último elemento.

Esta es la programación dinámica en su forma más simple: una relación de recurrencia más una tabla de respuestas a casos más pequeños. Hay n-1 sumas, un tiempo de O(n), y la tabla contiene n + 1 números, un espacio de O(n). n = 45 ahora requiere 44 sumas en lugar de miles de millones de llamadas.

Algoritmo

Si n es 0 o 1, devuelve n.
Crea una tabla de n + 1 números con f[0] = 0 y f[1] = 1.
Para i desde 2 hasta n, establece f[i] = f[i-1] + f[i-2].
Devuelve f[n].

def fib(n):
    if n < 2:
        return n
    f = [0] * (n + 1)  # f[i] will hold F(i)
    f[1] = 1
    for i in range(2, n + 1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]

Conserva solo los dos últimos números

Intuición

Observa qué lee el bucle de la tabla. Para completar f[i], necesita f[i-1] y f[i-2], y nada más antiguo, así que todas las posiciones anteriores son peso muerto. Usa dos variables en lugar de una tabla: prev contiene el número de dos pasos atrás y curr, el número de un paso atrás.

Empieza con prev = 0 y curr = 1, que son F(0) y F(1). En cada paso calcula next = prev + curr y después desplaza el par hacia delante: prev toma el valor anterior de curr, y curr toma next. Para n = 4, el par pasa de (0, 1) a (1, 1), (1, 2) y (2, 3), y curr = 3 es la respuesta.

El trabajo consiste en las mismas n-1 sumas, tiempo O(n), con tres enteros en memoria, espacio O(1). El orden de las actualizaciones importa: si sobrescribes prev antes de sumarlo, la suma usa el valor incorrecto.

Algoritmo

Si n es 0 o 1, devuelve n.
Establece prev = 0 y curr = 1.
Repite n-1 veces: calcula next = prev + curr, después establece prev = curr y curr = next.
Devuelve curr.

def fib(n):
    if n < 2:
        return n
    prev, curr = 0, 1  # F(0) and F(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

Errores comunes y casos límite

Fibonacci es el problema clásico de introducción a la programación dinámica, y la mayoría de los errores vienen de la recursión o de los dos primeros valores.

Entregar la solución con recursión ingenua. Pasa las pruebas pequeñas y después necesita miles de millones de llamadas en n = 45. Guarda los resultados en una tabla o en dos variables.
Empezar con valores incorrectos. Aquí, F(0) = 0 y F(1) = 1, así que F(2) = 1 y F(10) = 55. Empezar la secuencia en 1, 1 desplaza cada respuesta un índice.
Construir la tabla sin protegerse para valores pequeños de n. Para n = 0, una tabla de tamaño n + 1 = 1 no tiene espacio para f[1], y escribir ahí se sale de los límites. Devuelve n inmediatamente cuando n < 2.
Actualizar el par en el orden incorrecto. prev = curr seguido de curr = prev + curr suma el nuevo valor de prev y duplica curr. Calcula primero la suma en next, o usa una asignación simultánea si el lenguaje lo permite.
Ejecutar un paso de más. Un bucle que también calcula F(n+1) llega a F(46) = 1836311903 en el límite, lo cual todavía cabe en 32 bits solo por suerte. F(47) no.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la función recursiva de Fibonacci?

La recursión ingenua realiza 2 × F(n+1) - 1 llamadas, una cantidad que crece como 1.618^n y suele escribirse O(2^n). Para n = 45, son aproximadamente 3.7 × 10^9 llamadas. Almacenar cada resultado una sola vez, en una tabla o en dos variables, reduce la complejidad a O(n).

¿Cómo se resuelve Fibonacci con programación dinámica?

Comienza con la recurrencia F(n) = F(n-1) + F(n-2) y calcula los valores en orden creciente de n, almacenando cada uno. Puedes rellenar una tabla de abajo hacia arriba o conservar la función recursiva y almacenar en caché sus resultados, lo que se denomina memorización. De cualquier manera, cada valor se calcula una sola vez, así que el trabajo total es O(n).

¿Se puede calcular Fibonacci en espacio O(1)?

Sí. Cada número depende solo de los dos anteriores, así que bastan dos variables. Conserva los dos últimos valores y avánzalos en cada paso. Eso requiere un tiempo de O(n) y un espacio adicional de O(1).

¿Hay una forma más rápida que O(n)?

Sí. La matriz [[1, 1], [1, 0]] elevada a la potencia n contiene F(n) en su esquina superior derecha, y la potenciación por cuadrados repetidos calcula esa potencia con O(log n) multiplicaciones de matrices. También existe una fórmula cerrada con potencias de la proporción áurea, pero funciona con números de punto flotante y pierde precisión a medida que crece n, por lo que se prefieren los métodos con enteros.

Python

def fib(n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

n = 4

Esperado

Fibonacci Number

Función

Restricciones

Ejemplos

Pistas

Solución

Recursión directamente desde la definición

Rellena una tabla desde abajo hacia arriba

Conserva solo los dos últimos números

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares