"Para entender la recurrencia, primero hay que entender la recurrencia"
La recurrencia se presenta cuando un proceso se define basándose en función de si misma. Esto significa que una operación compleja se puede descomponer recursivamente en términos más sencillos, entonces los resultados parciales generados por las partes mas pequeñas se usan para encontrar la solución del problema completo.
El análisis de algoritmos es fundamental para entenderlos y aplicarlos en soluciones prácticas a problemas reales. Los aspectos que mas se estudian son el tiempo que tardan en ejecutarse, el rendimiento según los recursos de computación y el comportamiento en un nuevo entorno.
Las funciones recurrentes presentan grandes inconvenientes debido a que su tiempo de ejecución tiende fácilmente a valores muy grandes o a infinito, ésto puede generar problemas de desbordamiento de memoria, por lo tanto, es necesario limitar su comportamiento con valores asintótico dados por la notación de Landou o más conocida como notación O grande.
La complejidad con que se ejecuta un algoritmo depende del número de datos de entrada el cual debe ser un valor finito. La relación de recurrencia está dada de la forma:
donde a ≥ 1y b >1 ademas
Siguiente: Ejercicios resueltos usando Teorema Maestro
La recurrencia se presenta cuando un proceso se define basándose en función de si misma. Esto significa que una operación compleja se puede descomponer recursivamente en términos más sencillos, entonces los resultados parciales generados por las partes mas pequeñas se usan para encontrar la solución del problema completo.
El análisis de algoritmos es fundamental para entenderlos y aplicarlos en soluciones prácticas a problemas reales. Los aspectos que mas se estudian son el tiempo que tardan en ejecutarse, el rendimiento según los recursos de computación y el comportamiento en un nuevo entorno.
Las funciones recurrentes presentan grandes inconvenientes debido a que su tiempo de ejecución tiende fácilmente a valores muy grandes o a infinito, ésto puede generar problemas de desbordamiento de memoria, por lo tanto, es necesario limitar su comportamiento con valores asintótico dados por la notación de Landou o más conocida como notación O grande.
La complejidad con que se ejecuta un algoritmo depende del número de datos de entrada el cual debe ser un valor finito. La relación de recurrencia está dada de la forma:
- n es numero de datos que se analizan en todo el problema.
- a es el número de partes en que se ha dividido el problema para estudiarlo recursivamente.
- (n/b) tamaño de cada parte en que se ha dividido el problema, asumiendo el mismo tamaño para cada una.
- f(n) es el costo de realizar las llamadas recursivas, incluyendo el proceso de dividir y volver a unir las subtotales para obtener la solución total.
Siguiente: Ejercicios resueltos usando Teorema Maestro
1 comment:
Gracias por tu publicación, me sirvió para comprender la resolución de las recurrencias
Post a Comment