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 (ou tamanho) que o original, e então se aplica recursivamente o método até que o tamanho dos subproblemassub-problemas seja tratável. A solução de cada grupo de ''k'' subproblemassub-problemas divididos é combinada adequadamente até se ter a solução do problema original.

=={{Ver também}}==