Eso depende. Aquí hay tres respuestas diferentes.
La respuesta técnicamente correcta:
El programa (como se publica actualmente en los detalles de la pregunta) se ejecuta en tiempo constante porque solo declara la función fib pero nunca la llama.
- ¿Qué pasaría si pudiéramos demostrar que AGI está más allá del poder computacional de la máquina Turing?
- ¿Podría alguien ayudarme a determinar qué camino en mi educación se adaptaría mejor a mis intereses?
- ¿Es probable que los matemáticos y físicos también se destaquen en informática?
- ¿Cuál es la función concatenada en Excel y cuál es su opuesto?
- Si C / C ++ es más rápido, ¿por qué otros lenguajes no se compilan primero en C / C ++ y solo después en el código de máquina?
Como dicen, “técnicamente correcto es el mejor tipo de correcto!” 🙂
Aún así, la respuesta anterior claramente no es lo que quería escuchar. Por lo tanto, para el resto de mi respuesta, supongo que agregamos una llamada real de la función recursiva. Por ejemplo, print( fib( int(input()) ) ) .
La respuesta general:
La parte que debería ser fácil de observar es que si ejecutamos el programa en la entrada x , ejecutará los pasos lógicos [math] \ Theta (x) [/ math]. Más precisamente, está claro que la línea memo[n] = fib(n-1) + fib(n-2) se ejecutará exactamente x- 1 veces: una vez para cada entrada de 2 a x . Por lo tanto, el número total de llamadas a funciones es lineal en x . Esa es nuestra segunda respuesta: el programa realiza pasos lógicos [matemáticos] \ Theta (x) [/ matemáticos].
La respuesta donde los detalles de implementación son importantes:
Ahora para la tercera respuesta. Claro, solo realizamos adiciones x -1. Pero, ¿es correcto afirmar que el programa se ejecuta en tiempo lineal? Realmente no.
El problema es que los números de Fibonacci crecen exponencialmente. Esto significa que los números superarán muy rápidamente el tamaño de una palabra de máquina, y más allá de ese punto, no podemos afirmar realmente que podemos agregar dos números en tiempo constante. En cambio, el tiempo necesario para sumar dos números grandes es proporcional al número de dígitos del resultado.
Por lo tanto, el tiempo total de ejecución de nuestro programa es proporcional al número total de dígitos en [math] F_2, F_3, \ dots, F_x [/ math].
El i -ésimo número de Fibonacci es proporcional a [matemática] \ phi ^ i [/ matemática], donde [matemática] \ phi = (1+ \ sqrt {5}) / 2 [/ matemática] es la proporción áurea. Por lo tanto, el número de dígitos en [math] F_i [/ math] es proporcional a i. Por lo tanto, el número total de dígitos en [matemáticas] F_2, F_3, \ puntos, F_x [/ matemáticas] es cuadrático en x .
Así que esa es nuestra respuesta final: para calcular el número x de Fibonacci, la recursión memorizada debe realizar [matemáticas] \ Theta (x ^ 2) [/ matemáticas] pasos elementales de cálculo.
También tenga en cuenta que el programa realmente almacena todos los valores intermedios en el diccionario. Por lo tanto, si lo usa para calcular fib(x) , consumirá [math] \ Theta (x ^ 2) [/ math] bytes de memoria. Ese será el principal cuello de botella en la práctica.
