Sunday, March 04, 2012

Ejemplos resueltos sobre analisis iterativo de la complejidad de algoritmos recursivos

"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
  • 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.
Los siguientes son 4 ejemplos de como analizar paso a paso  la complejidad del tiempo de ejecución en algoritmos recursivos:


Siguiente: Ejercicios resueltos usando  Teorema Maestro

Si tienes información adicional sobre este tema, tus comentarios o enlaces de referencia serán bienvenidos.

1 comment:

Anonymous said...

Gracias por tu publicación, me sirvió para comprender la resolución de las recurrencias