Divisão e conquista: diferenças entre revisões

Esta técnica consiste em dividir sucessivamente o problema em problemas menores até que uma solução simples exista, de forma que a combinação simples destas soluções parciais forme a solução completa do problema. É o que se faz com todos os problemas complexos em geral. Como algoritmo, entretanto, cabe uma definição mais precisa. Dado um problema a ser resolvido para n entradas, o algoritmo divide as entradas em k grupos distintos, gerando k novos problemas. Freqüentemente estes problemas são do mesmo tipo do original, e então se aplica recursivamente o método até que o tamanho dos subproblemas seja tratável. A solução de cada grupo de k subproblemas divididos é combinada adequadamente até se ter a solução do problema original.