Divisão e conquista
Nota: Se procura o conceito político, veja dividir para conquistar. | Este artigo não cita fontes confiáveis. (Janeiro de 2020) |
Divisão e Conquista (do inglês Divide and Conquer) em computação é uma técnica de projeto de algoritmos utilizada pela primeira vez por Anatolii Karatsuba em 1960 no algoritmo de Karatsuba.
Técnica[editar | editar código-fonte]
Esta técnica consiste em dividir um problema maior recursivamente em problemas menores até que o problema possa ser resolvido diretamente. Então a solução do problema inicial é dada através da combinação dos resultados de todos os problemas menores computados. Vários problemas podem ser solucionados através desta técnica, como a ordenação de números através do algoritmo merge sort e a transformação discreta de Fourier através da transformada rápida de Fourier. Outro problema clássico que pode ser resolvido através desta técnica é a Torre de Hanoi.
A técnica soluciona o problema através de três fases:
- Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva.
- Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
- Combinação: o resultado dos problemas menores são combinados até que seja obtida a solução do problema maior.
Eficiência[editar | editar código-fonte]
Problemas que utilizam esta técnica podem tirar proveito de máquinas com múltiplos processadores pois a fase de divisão em problemas menores proporciona uma divisão natural do trabalho. Cada um dos problemas menores obtidos pode ser calculado separadamente em um processador sem depender dos demais.
A solução por esta técnica também é eficiente no uso da memória cache pois ao final da fase de divisão grande parte dos dados necessários para a fase de combinação já estão disponíveis na cache proporcionando um acesso mais veloz aos dados. Porém o caráter recursivo das soluções acaba gerando um trabalho de processamento maior devido ao uso de chamadas recursivas e o uso da pilha de chamadas.