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.
Aplicação da Abordagem Dividir e Conquistar
A seguir estão alguns problemas, que são resolvidos usando a abordagem de dividir para conquistar.
- Encontrar o máximo e o mínimo de uma sequência de números
- Multiplicação da matriz de Strassen
- Mesclar classificação
- Busca binária