Diferencias

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

--- algoritmos-oia:divide-and-conquer [2017/12/23 14:11]
brianbok creado
+++ algoritmos-oia:divide-and-conquer [2018/01/22 14:32] (actual)
35.226.23.240 ↷ Links adapted because of a move operation
@@ Línea 1: / Línea 1: @@
-Es una técnica que consiste en resolver problemas de forma [[algoritmos-oia:recur|recursiva]] partiendo un problema en uno o más problemas más chicos.
+====== Introducción ======
+Es una técnica que consiste en resolver problemas de forma [[algoritmos-oia:recursion|recursiva]] partiendo un problema en uno o más problemas más chicos.
 Identificamos dos partes:
   * __Divide:__ Las llamadas recursivas a problemas más chicos
   * __Conquer:__ Formación de la solución al problema original
+====== Ejemplo: Merge Sort ======
+En el algoritmo de [[algoritmos-oia:ordenamiento:merge-sort|merge sort]] utilizamos la técnica de Divide & Conquer.
+  * __Divide:__ Llamadas a sort de las dos mitades del arreglo
+  * __Conquer:__ Construcción del ordenamiento a partir de las dos mitades, etapa de merge
+====== Complejidad en D&C ======
+  * Ad-Hoc / Árbol de Ejecución
+  * Método de sustitución
+  * [[algoritmos-oia:teorema-maestro|Teorema maestro]]
+====== Ejemplos de algoritmos/problemas con D&C ======
+  * Solución $O(n log n)$ a maximum subarray
+  * Karatsuba y Strassen
+====== Continuar leyendo ======
+  * D&C sobre árboles
+  * Programación Dinámica

OIA-Wiki