Ruben Ramirez
Pregunta#use este codigo(use recursividad) para calcular los 50 priimeros numeros de fibonacci y mi computadora fue demorando mucho, de forma exponencial, a media que imprimia los numeros. Entonces mi pregunta es: que tan efiiciente es usar recursividad o como es su complejidad
fibonacci = lambda x: 0 if x== 0 else 1 if x<3 else fibonacci(x-1)+ fibonacci(x-2)
for n in range(0,50):
print(fibonacci(n))
- O(1): constante, el tiempo de ejecución no depende del tamaño de la entrada
- O(log n): logarítmica, el tiempo de ejecución crece lentamente con el tamaño de la entrada
- O(n): lineal, el tiempo de ejecución aumenta proporcionalmente al tamaño de la entrada
- O(n log n): log-lineal, el tiempo de ejecución aumenta un poco más rápido que linealmente con el tamaño de la entrada
- O(n^2): cuadrática, el tiempo de ejecución aumenta rápidamente con el tamaño de la entrada
- O(2^n): exponencial, el tiempo de ejecución aumenta extremadamente rápido con el tamaño de la entrada.
Francisco Ponce
Esto es un tema de complejidad algorítmica y es un poco avanzado en programación, pero muy necesario para proponer soluciones a problemas teniendo en cuenta la escalabilidad de un algoritmo.
La complejidad algorítmica es una medida de cuánto tiempo y espacio utiliza un algoritmo para resolver un problema dado. Se utiliza para comparar la eficiencia de diferentes algoritmos que resuelven el mismo problema.
La complejidad temporal se refiere al tiempo que tarda un algoritmo en ejecutarse y se mide en función del tamaño de la entrada. Por ejemplo, si un algoritmo toma 1 segundo para procesar un conjunto de datos de tamaño n, y 2 segundos para procesar un conjunto de datos de tamaño 2n, entonces su complejidad temporal es O(n).
La complejidad espacial se refiere al espacio de almacenamiento que un algoritmo utiliza y se mide en función del tamaño de la entrada. Por ejemplo, si un algoritmo utiliza 1 GB de memoria para procesar un conjunto de datos de tamaño n, y 2 GB de memoria para procesar un conjunto de datos de tamaño 2n, entonces su complejidad espacial es O(n).
Algunas de las complejidades algorítmicas más comunes son:
Regresando al ejercicio, la complejidad temporal de la función de Fibonacci recursiva es de O(2^n), ya que para cada llamada recursiva se realizan dos llamadas adicionales. Esto significa que el tiempo de ejecución aumenta exponencialmente a medida que aumenta el valor de n.
La razón por la que tu computadora se demoró tanto al calcular los primeros 50 números de Fibonacci utilizando recursión es debido a que está recalculando los mismos valores varias veces, lo que hace que el tiempo de ejecución sea mucho más alto de lo necesario. Esto se conoce como "llamadas redundantes" en la recursión.
