Diferencias

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

--- algoritmos-oia:programacion-dinamica [2017/12/23 13:48]
brianbok [Explicación]
+++ algoritmos-oia:programacion-dinamica [2017/12/23 14:05] (actual)
brianbok [**Costo total = #Subproblemas $\times$ Costo por subproblema **]
@@ Línea 270: / Línea 270: @@
 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