Soluciones efectivas a la secuencia de Fibonacci y su análisis de complejidad temporal【3】

.....Continuó con la última solución válida de la Serie 2 de Análisis de Secuencia de Fibonacci y Complejidad del Tiempo.

6.? Solución práctica para la recursividad sin cola

Como se mencionó anteriormente, la complejidad temporal de la solución recursiva típica de la secuencia de Fibonacci es O (1.618n), que aumenta exponencialmente y no tiene valor práctico.

Si observa atentamente el proceso de llamada recursiva, encontrará que el proceso recursivo binario de calcular_Fibonacci_sequence(n-1)+calculate_Fibonacci_sequence(n-2) tendrá muchos resultados intermedios repetidos.

Luego, durante el proceso de recursividad, guarde los resultados intermedios en un diccionario y verifique en el diccionario si cada llamada recursiva es una llamada con los mismos parámetros; de ser así, regrese directamente y guárdela en el diccionario. valor.

De esta forma, la complejidad temporal del algoritmo se reduce a O(n). Mediante la tecnología de almacenamiento en caché, la complejidad del tiempo se reduce a un nivel utilizable.

Empiece a escribir este decorador de caché recursivo. Los decoradores se utilizan ampliamente en Python, lo que facilita la cascada modular en muchas situaciones.

Probemos el efecto y contemos los elementos 100.

La situación de estancamiento original desapareció y salió en unos segundos.

Bien, intenta calcular el elemento 1200 nuevamente.

Error de desbordamiento de pila

Esto también es una barrera para la practicidad. El espacio de pila predeterminado de Python no es grande, solo 1000. Python oficialmente no recomienda la recursividad, intente escribirlo como un bucle iterativo. La idea oficial es establecer un pequeño espacio de pila de forma predeterminada. Si un programa tiene una recursividad demasiado profunda, puede exponerse y reescribirse al principio del tiempo de ejecución.

Pero a veces la forma recursiva de escribir es realmente concisa y clara, y aún se puede utilizar cuando no hay requisitos de eficiencia.

Entonces, una solución al error de desbordamiento durante el proceso recursivo es aumentar dinámicamente el valor límite establecido.

Se podría pensar que usar un decorador es una forma elegante de lograrlo.

Sin embargo, si se considera que el valor original de recursionlimit debe restaurarse después de que se ejecute la función recursiva.

El decorador no puede simplemente lograr este objetivo por sí solo (si tiene alguna buena idea, deje un comentario a continuación para discutir_)

Implementé esta solución pasando parámetros de función.

Probémoslo.

El tiempo de ejecución es el mismo que el ejemplo anterior, tiempo total: 0,012642 segundos.

Resolución de problemas

Hacer que la solución recursiva de la secuencia de Fibonacci que no tiene valor práctico se convierta en una solución recursiva utilizable.

Continuará.

Solución eficiente y análisis de complejidad temporal serie 4 de los números de Fibonacci