DAA - Divide y vencerás
Muchos algoritmos son de naturaleza recursiva para resolver un problema dado que trata de manera recursiva con subproblemas.
En divide and conquer approach, un problema se divide en problemas más pequeños, luego los problemas más pequeños se resuelven de forma independiente y, finalmente, las soluciones de problemas más pequeños se combinan en una solución para el problema grande.
Generalmente, los algoritmos de divide y vencerás tienen tres partes:
Divide the problem en una serie de subproblemas que son instancias más pequeñas del mismo problema.
Conquer the sub-problemsresolviéndolos de forma recursiva. Si son lo suficientemente pequeños, resuelva los subproblemas como casos base.
Combine the solutions a los subproblemas en la solución del problema original.
Pros y contras del enfoque de dividir y conquistar
El enfoque de dividir y conquistar apoya el paralelismo ya que los subproblemas son independientes. Por lo tanto, un algoritmo diseñado con esta técnica puede ejecutarse en el sistema multiprocesador o en diferentes máquinas simultáneamente.
En este enfoque, la mayoría de los algoritmos se diseñan mediante recursividad, por lo que la gestión de la memoria es muy alta. Para la función recursiva, se usa la pila, donde se debe almacenar el estado de la función.
Aplicación del enfoque de divide y vencerás
A continuación se presentan algunos problemas, que se resuelven utilizando el enfoque de divide y vencerás.
- Encontrar el máximo y el mínimo de una secuencia de números
- Multiplicación de matrices de Strassen
- Combinar ordenación
- Búsqueda binaria