La estrategia de Divide y Vencerás es una técnica algorítmica que se basa en la descomposición de un problema en subproblemas de su mismo tipo, lo que permite disminuir la complejidad y en algunos casos, paralelizar la resolución de los mismos.
La estrategia del algoritmo es la siguiente:
Desde un punto de vista algorítmico, en la primera de las fases se determina el número y tamaño de los subproblemas, siendo éste uno de los pasos determinantes para la complejidad posterior del algoritmo. Seguidamente se realizan llamadas recursivas al algoritmo para cada uno de los subproblemas. Por último, si es necesario, se combinan las soluciones parciales y se obtiene la solución del problema.
Si quieres profundizar más sobre la técnica de Divide y Vencerás, dispones de más información aquí.
A continuación se muestra una lista de ejemplos. Puedes acceder a cada uno de ellos desde el menú superior.
El algoritmo Mergesort es un ejemplo sencillo para entender la técnica de divide y vencerás. Dado un vector de enteros, lo que plantea es dividir el vector por la mitad e invocar al algoritmo para ordenar cada mitad por separado. Tras ésta operación, sólo queda fusionar esos dos subvectores ordenados en uno sólo, también ordenado.
La fusÍón (merge) se hace tomando, sucesivamente, el menor elemento de entre los que queden en cada uno de los dos subvectores.
En Quicksort se pone el énfasis en cómo combinar los subproblemas resueltos, mientras que la operación de descomponer en subproblemas es trivial. Sin embargo, si al descomponer el vector, los elementos del primer subvector fueran todos menores o iguales que los del segundo subvector, no habría que realizar ninguna operación de combinación. En este caso, la descomposición es algo más compleja, pero la combinación es trivial.
Esta es la idea que subyace al algoritmo quicksort.
Dado un vector de números enteror, este problema consiste en averiguar si hay algún elemento que aparezca más de la mitad del número de elementos del vector. El algoritmo divide el vector en dos mitades y resuelve cada una por separado. A la hora de combinar las dos mitades, el algoritmo indicará el algoritmo mayoritario de la combinación o dirá que no existe.