Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa Próxima revisión Ambos lados, revisión siguiente | ||
algoritmos-oia:programacion-dinamica [2017/12/23 01:58] brianbok [Solución recursiva] |
algoritmos-oia:programacion-dinamica [2017/12/23 14:04] brianbok [Resumen: importante] |
||
---|---|---|---|
Línea 180: | Línea 180: | ||
Luego nos queda | Luego nos queda | ||
- | $f(i, j) := min{f(i-1, j) + M[i][j], f(i, j-1) + M[i][j])$ | + | $f(i, j) = min\{f(i-1, j) + M[i][j], f(i, j-1) + M[i][j]\}$ |
===== Código Top-Down ===== | ===== Código Top-Down ===== | ||
Línea 239: | Línea 239: | ||
===== Problemas Relacionados ===== | ===== Problemas Relacionados ===== | ||
- | Al-Garin | ||
+ | [[http://juez.oia.unsam.edu.ar/#/task/algarin/statement|Al-Garin]] | ||
====== Complejidad en dinámica ====== | ====== Complejidad en dinámica ====== | ||
===== Complejidad en Bottom-Up ===== | ===== Complejidad en Bottom-Up ===== | ||
Línea 246: | Línea 246: | ||
===== Complejidad en Top-Down ===== | ===== Complejidad en Top-Down ===== | ||
- | Para top-down es menos evidente como hacer el análisis de complejidad | + | Para top-down es menos evidente como hacer el análisis de complejidad. |
+ | El motivo de la dificultad radica es no poder precisar el orden de ejecución, por la memoization. | ||
+ | No sabemos "en qué momento" se hace por primera vez un cálculo, solo sabemos que se hace y solo una vez. | ||
+ | |||
+ | Tenemos dos tipos de llamadas a la funciones memoizadas: | ||
+ | A) La primer llamada a ese subproblema (la primer llamada con esos parámetros) | ||
+ | B) La segunda llamada o posteriores | ||
+ | |||
+ | Cuando tomamos el costo de una llamada de tipo A), no contamos la recursión como parte del costo, tomamos cada llamada recursiva como $O(1)$ ya que las vamos a tomar como costo de otro subproblema, o de B) | ||
+ | |||
+ | Para medir la complejidad total sumamos todos los costos de resolver cada subproblema. | ||
+ | De forma simplificada, solo contamos el costo de las llamadas de tipo A) obtieniendo | ||
+ | |||
+ | Costo total = #Subproblemas $\times$ Costo A) | ||
+ | |||
+ | ==== Explicación ==== | ||
+ | |||
+ | ¿Donde esta el costo de las llamadas de tipo B)? | ||
+ | Cada llamada B) la hizo algún A) mientras estaba computando | ||
+ | Luego, el costo de hacer esa llamada se lo podemos cobrar dentro del costo de resolver A) | ||
+ | El costo total será | ||
+ | $Subproblemas \times ( Costo(A) + llamadas recursivas \times Costo(B)) $ | ||
+ | |||
+ | Asumiendo que todas las llamadas recursivas son de tipo B) para acotar peor caso | ||
+ | Por ejemplo, en el problema de camino en la matriz queda: | ||
+ | |||
+ | $O(n^2) \times ( O(1) + O(1) \times O(1)) $ | ||
+ | |||
+ | Podemos ver que la cantidad de llamadas recursivas siempre va a estar contenida en la complejidad de A). No podría ser que tengamos que hacer $O(n)$ llamadas pero costo(A) = $O(log n)$ operaciones, ya que las llamadas recursivas son parte del costo(A). Además Costo(B) suele ser O(1), por lo cual podemos simplificar y queda | ||
+ | $Subproblemas \times ( Costo(A))$ | ||
+ | ==== Resumen: importante ==== | ||
+ | |||
+ | En general lo que llamamos Costo(A) se denota como Costo por subproblema, y podemos confiar *casi ciegamente* en la fórmula: | ||
+ | |||
+ | __ **Costo total = #Subproblemas $\times$ Costo por subproblema **__ | ||
====== Material extra ====== | ====== Material extra ====== | ||
Línea 255: | Línea 289: | ||
===== Fácil ===== | ===== Fácil ===== | ||
- | [[http://juez.oia.unsam.edu.ar/#/task/algarin/statement|Al-Garin]] | ||
===== Medio ===== | ===== Medio ===== | ||
===== Difícil ===== | ===== Difícil ===== | ||
[[http://juez.oia.unsam.edu.ar/#/task/zapallos/statement| Zapallos]] | [[http://juez.oia.unsam.edu.ar/#/task/zapallos/statement| Zapallos]] |