Divisão e conquista

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 o da ordenação de números através do algoritmo merge sort e da 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:

  1. Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva.
  2. Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
  3. 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.

Ver também[editar | editar código-fonte]