Diferencias

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

--- algoritmos-oia:programacion-dinamica [2017/12/23 03:29]
brianbok [Explicación]
+++ algoritmos-oia:programacion-dinamica [2017/12/23 14:05] (actual)
brianbok [**Costo total = #Subproblemas $\times$ Costo por subproblema **]
@@ Línea 263: / Línea 263: @@
 ==== Explicación ====
-¿Donde esta el costo de las llamadas de tipo B)? Las cobramos en A)!
+¿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