## 2.1 DIVIDE Y VENCERÁS

Muchos algoritmos útiles tienen una estructura recursiva, de modo que para resolver un problema se llaman recursivamente a sí mismos una o más veces para solucionar subproblemas muy similares. Esta estructura obedece a una estrategia divide y vencerás, también llamada dividir y conquistar, en que se ejecuta tres pasos en cada nivel de la recursión:

• Dividir. Dividen el problema en varios subproblemas similares al problema original pero de menor tamaño;

• Conquistar. Resuelven recursivamente los subproblemas si los tamaños de los subproblemas son suficientemente pequeños, entonces
resuelven los subproblemas de manera directa; y luego,

• Combinar. Combinan estas soluciones para crear una solución al problema original.

La técnica Divide y Vencerás consiste en descomponer el caso que hay que resolver en subcasos más pequeños, resolver independientemente los subcasos y por último combinar las soluciones de los subcasos para obtener la solución del caso original.

Caso General

Consideremos un problema arbitrario, y sea A un algoritmo sencillo capaz de resolver el problema. A debe ser eficiente para casos pequeños y lo denominamos subalgoritmo básico.

El caso general de los algoritmos de Divide y Vencerás (DV) es como sigue:

función DV(x)
{
si x es suficientemente pequeño o sencillo entonces
devolver A(x)
descomponer x en casos más pequeños x1, x2, x3 , ... , xl
para i ← 1 hasta l hacer
yi ← DV(xi)
recombinar los yi para obtener una solución y de x
devolver y
}

El número de subejemplares l suele ser pequeño e independiente del caso particular que haya que resolverse.

Para aplicar la estrategia Divide y Vencerás es necesario que se cumplan tres condiciones:

- La decisión de utilizar el subalgoritmo básico en lugar de hacer llamadas recursivas debe tomarse cuidadosamente.
- Tiene que ser posible descomponer el caso en subcasos y recomponer las soluciones parciales de forma eficiente.
- Los subcasos deben ser en lo posible aproximadamente del mismo tamaño.

En la mayoría de los algoritmos de Divide y Vencerás el tamaño de los l subcasos es aproximadamente m/b, para alguna constante b, en donde m es el tamaño del caso (o subcaso) original (cada subproblema es aproximadamente del tamaño 1/b del problema original).

El análisis de tiempos de ejecución para estos algoritmos es el siguiente:
Sea g(n) el tiempo requerido por DV en casos de tamaño n, sin contar el tiempo necesario para llamadas recursivas. El tiempo total t(n) requerido por este algoritmo de Divide y Vencerás es parecido a:

t(n) = l t(n/ b) + g(n) para l ≥ 1 y b ≥ 2 siempre que n sea suficientemente grande. Si existe un entero k ≥ 0 tal que: g(n) ∈ Θ (nk),

Se puede concluir que: t(n) ∈

- Θ(nk) si l < bk
- Θ(nk log n) si l = bk
- Θ(nlogbl) si l > bk

###