Please enable JavaScript.
Coggle requires JavaScript to display documents.
PROGRAMACION DINAMICA - Coggle Diagram
PROGRAMACION DINAMICA
Definición
Técnica de diseño de algoritmos para evaluar ecuaciones de recurrencia eficientemente
Enfoque hacia arriba (Bottom-up): De los casos base a soluciones mayores
Diferencia con Dividir y Conquistar
Dividir y Conquistar (Enfoque hacia abajo): Divide en subproblemas independientes
Programación Dinámica: Resuelve problemas con subproblemas solapados
Propiedades para su aplicación
Solución expresable mediante ecuación de recurrencia
Presencia de invocaciones duplicadas con idénticos parámetros
Ideas Fundamentales
Uso de estructura de datos (Memoria) para valores ya calculados
Evaluación incremental de subproblemas de menor a mayor tamaño
Ejemplos Clásicos analizados
Sucesión de Fibonacci
Recurrencia: fib(n) = fib(n-1) + fib(n-2)
Ineficiencia recursiva: Complejidad exponencial O(2^n)
Solución Dinámica: Complejidad polinómica Θ(n)
Distancia de Edición
Objetivo: Mínimo número de cambios (insertar, eliminar, sustituir)
Recurrencia: Basada en comparar caracteres finales
Complejidad Dinámica: O(mn) usando matriz bidimensional
Ventajas
Reducción considerable de la complejidad temporal (de exponencial a polinómica)
Algoritmos generalmente iterativos