DAA - Divide & Conquer

Muitos algoritmos são recursivos por natureza para resolver um determinado problema, lidando recursivamente com subproblemas.

No divide and conquer approach, um problema é dividido em problemas menores, então os problemas menores são resolvidos independentemente e, finalmente, as soluções de problemas menores são combinadas em uma solução para o problema maior.

Geralmente, os algoritmos de divisão e conquista têm três partes -

Divide the problem em uma série de subproblemas que são instâncias menores do mesmo problema.
Conquer the sub-problemsresolvendo-os recursivamente. Se eles forem pequenos o suficiente, resolva os subproblemas como casos básicos.
Combine the solutions para os subproblemas na solução para o problema original.

Prós e contras da abordagem dividir e conquistar

A abordagem de divisão e conquista suporta paralelismo, pois os subproblemas são independentes. Portanto, um algoritmo, que é projetado usando essa técnica, pode ser executado no sistema multiprocessador ou em diferentes máquinas simultaneamente.

Nesta abordagem, a maioria dos algoritmos são projetados usando recursão, portanto, o gerenciamento de memória é muito alto. Para a pilha de função recursiva é usada, onde o estado da função precisa ser armazenado.