Diferencias

Muestra las diferencias entre dos versiones de la página.

--- algoritmos-oia:programacion-dinamica [2017/12/23 02:10]
brianbok [Complejidad en Top-Down]
+++ algoritmos-oia:programacion-dinamica [2017/12/23 14:05] (actual)
brianbok [**Costo total = #Subproblemas $\times$ Costo por subproblema **]
@@ Línea 264: / Línea 264: @@
 ¿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 ======

OIA-Wiki