Introducción
Last updated
Last updated
Es una técnica de diseño de algoritmos que consiste en resolver un problema a partir de la solución de subproblemas del mismo tipo y de menor tamaño.
Si los subproblemas son todavía relativamente grandes se aplicará de nuevo esta técnica hasta alcanzar subproblemas lo suficientemente pequeños para ser solucionados directamente.
Todo ello, naturalmente, sugiere el uso de recursión.
La resolución de un problema mediante esta técnica consta fundamentalmente de los siguientes pasos:
Dividir el problema en a subproblemas del mismo tipo, pero de menor tamaño.
Resolver independientemente todos los subproblemas.
Por último, combinar las soluciones obtenidas en el paso anterior para construir la solución del problema original.
En cuanto a la eficiencia hay que tener en consideración un factor importante durante el diseño del algoritmo: el número de subproblemas y su tamaño, pues esto influye de forma notable en la complejidad temporal del algoritmo resultante.
El número a de subproblemas debe ser pequeño.
Es importante conseguir que los subproblemas sean independientes, es decir, que no haya solapamiento entre ellos.
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:
donde a>0, c>0, k 0 y b>1.
El valor de a representa el número de subproblemas, n/b es el tamaño de cada uno de ellos y representa el coste de descomponer y combinar o bien el de resolver un problema elemental.
La solución a esta ecuación puede alcanzar distintas complejidades, siendo estas:
Las diferencias surgen de los distintos valores que pueden tomar a y b, es decir, número de subproblemas y su tamaño.
Lo importante es observar que en todos los casos la complejidad temporal es de orden polinómico o polilogarítmico pero nunca exponencial frente a algoritmos recursivos que pueden alcanzar esta complejidad en muchos casos.
