====== 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