Divide y Vencerás

Dividir y vencer es la base de varios algoritmos eficientes para casi cualquier tipo de problema como, por ejemplo, algoritmos de ordenamiento (mergesort, quicksort, entre otros), multiplicar números grandes (Karatsuba), análisis sintácticos (top-down), la transformada discreta de Fourier, multiplicación rápida de matrices (Strassen), etc.

Analizar y diseñar algoritmos de DyV son tareas que lleva tiempo dominar. Al igual que en la inducción, a veces es necesario sustituir el problema original por uno más complejo para conseguir realizar la recursión, y no hay un método sistemático de generalización.

Divide y Vencerás

“El método divide y vencerás consiste en descomponer el problema en una serie de subproblemas de menor tamaño, al resolver estos subproblemas usando siempre la misma técnica, las soluciones parciales se combinan para obtener la solución del problema original”.

"Tenemos un problema complejo al cual dividimos en subproblemas mas pequeños a resolver. Para resolver cada subproblema seguimos el mismo procedimiento hasta que llegamos a un problema que es trivial. Una vez resueltos los subproblemas los combinamos para dar solución al problema original". 

De esta forma DyV se expresa de manera natural mediante un algoritmo recursivo.

Para que la aplicación del método divide y vencerás, convenga debe cumplirse que

1.Las operaciones descomponer y combinar deben ser bastante eficientes.
2.El número de subproblemas generados sea pequeño
3.Los subproblemas sean aproximadamente del mismo tamaño y no solapen entre sí.

La función complejidad para un problema de tamaño n es un sistema de ecuaciones recurrentes de la forma:

Si el problema 𝑥 es de tamaño 𝑛, y los tamaños de los subproblemas 𝑥1, 𝑥2, … , 𝑥𝑘 son, respectivamente, 𝑛1, 𝑛2, … , 𝑛𝑘, podemos describir el coste en tiempo del algoritmo divide_y_venceras mediante la siguiente recurrencia:

Donde 𝑻(𝒏) es el tiempo del algoritmo divide_y_venceras, 𝒇(𝒏) es el tiempo que toma combinar las soluciones y 𝒈(𝒏) es el tiempo del metodo_directo.

Complejidad de Divide y Vencerás

El diseño Divide y Vencerás produce algoritmos recursivos cuyo tiempo de ejecución se puede expresar mediante una ecuación en recurrencia del tipo:

𝒂, 𝒄 𝒚 𝒌 son números reales 

𝒏 y 𝒃 son números naturales, 

𝒂 > 𝟎, 𝒄 > 𝟎, 𝒌 ≥ 𝟎 𝒚 𝒃 > 𝟏 

𝒂 representa el número de subproblemas. 

𝒏/𝒃 es el tamaño de cada uno de ellos. 

𝒄𝒏 𝒌 representa el coste de descomponer el problema inicial en los 𝑎 subproblemas y el de combinar las soluciones para producir la solución del problema original, o bien el de resolver un problema elemental. 

La solución a esta ecuación, puede alcanzar distintas complejidades.

Las diferencias surgen de los distintos valores que pueden tomar 𝑎 y 𝑏, que en definitiva determinan el número de subproblemas y su tamaño. Lo importante es observar que en todos los casos la complejidad es de orden polinómico o polilogarítmico pero nunca exponencial.

Los algoritmos recursivos pueden alcanzar una complejidad exponencial en muchos casos. Esto se debe normalmente a la repetición de los cálculos que se produce al existir solapamiento en los subproblemas en los que se descompone el problema original.

Ejemplo 1. Búsqueda del máximo y del mínimo

Operación básica. Asignaciones a Max, Min, Max1, Min1, Max2 y Min2

Complejidad Temporal

          Peor caso: Los números están hasta el final el máximo y el mínimo

En el ejemplo anterior la complejidad temporal no obtuvo un beneficio al utilizar un algoritmo que emplea la técnica de DyV, si se piensa como una aplicación a funcionar bajo la idea de un proceso monoprocesador, pero si se considera que la solución de los problemas parciales es independiente y se utiliza una idea de procesamiento paralelo, probablemente el potencial de un algoritmo como este se vera reflejado en los tiempos de procesamiento de problemas para “n” muy grandes.

Ejemplo 2. Ordenamiento de un arreglo

Operación básica. Movimientos en el arreglo y comparaciones entre un elemento y "temp"

Complejidad temporal.

             Peor caso: Los números están ordenados y se compara un elemento con todos los elementos                                  del arreglo