Herramientas de usuario
algoritmos-oia:programacion-dinamica
Diferencias
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 | ||
|
algoritmos-oia:programacion-dinamica [2017/12/23 02:07] brianbok [Complejidad en Top-Down] |
algoritmos-oia:programacion-dinamica [2017/12/23 14:05] (actual) brianbok [**Costo total = #Subproblemas × Costo por subproblema **] |
||
|---|---|---|---|
| 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 253: | Línea 253: | ||
| A) La primer llamada a ese subproblema (la primer llamada con esos parámetros) | A) La primer llamada a ese subproblema (la primer llamada con esos parámetros) | ||
| B) La segunda llamada o posteriores | B) La segunda llamada o posteriores | ||
| - | | + | |
| - | Para medir la complejidad sumamos todos los costos de resolver cada subproblema. | + | 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 | De forma simplificada, solo contamos el costo de las llamadas de tipo A) obtieniendo | ||
| Costo total = #Subproblemas × Costo A) | Costo total = #Subproblemas × 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×(Costo(A)+llamadasrecursivas×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(n2)×(O(1)+O(1)×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(logn) 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×(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 × Costo por subproblema ** | ||
| + | |||
| ====== Material extra ====== | ====== Material extra ====== | ||
| Línea 266: | Línea 290: | ||
| ===== 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]] | ||
algoritmos-oia/programacion-dinamica.1513994820.txt.gz · Última modificación: 2017/12/23 02:07 por brianbok
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
