- Qual a diferença entre as técnicas de design de algoritmo
Divide and Conquer
eDecrease and Conquer
? - A
divide
é recursiva e adecrease
não? - Algum exemplo para a
decrease
? - E
dynamic programming
?
1 Resposta
Olá! Primeiro é importante observar que todas essas técnicas são baseadas em indução.
Divide and conquer
é uma técnica de projeto de algoritmos que consiste em dividir o problema em subproblemas menores. Esses algoritmos são divididos em duas fases: divisão
e conquista
. Na divisão
, dividimos o problema ao meio (ou em alguma fração) e resolvemos cada subproblema. Na fase de conquista
, combinamos as soluções dos subproblemas para obter a solução para o problema total. Exemplos de algoritmos que usam essa técnica são o MergeSort
e o QuickSort
.
Decrease and conquer
é semelhante à divide and conquer
, com a diferença de que nessa técnica a fase de decrease
apenas diminui o problema, gerando um subproblema menor (ao invés de dividir em vários subproblemas). Após resolver o subproblema menor, a fase de conquista
é executada para utilizar a solução do subproblema para obter a solução do problema total. Exemplos de algoritmos de decrease and conquer
são Busca Binária
(dividimos o vetor no meio e executamos a busca apenas em um dos lados) e DFS
. Algoritmos de decrease and conquer
também podem ser recursivos, a exemplo da busca binária.
Já a programação dinâmica é uma técnica que utiliza memorização para resolver subproblemas. Essa técnica faz sentido quando subproblemas se repetem. Um exemplo de problema que pode ser resolvido com programação dinâmica é o fibonacci
, pois, fibonacci(N) = fibonacci(N-1) + fibonacci(N-2)
, fibonacci(N-1) = fibonacci(N-2) + fibonacci(N-3)
, e assim por diante... Note que o subproblema fibonacci(N-2)
se repete. A programação dinâmica consiste em memorizar as solução dos subproblemas para que não sejam recalculados.
Outra coisa importante é que a programação dinâmica só pode ser aplicada a problemas com subestrutura ótima. Dizer que um problema tem subestrutura ótima significa que uma solução ótima para o problema maior contém as soluções ótimas para os subproblemas.
Estou deixando algumas referências com explicações mais detalhadas.
https://www.geeksforgeeks.org/decrease-and-conquer/
https://stackoverflow.com/questions/13538459/difference-between-divide-and-conquer-algo-and-dynamic-programming
https://pt.wikipedia.org/wiki/Programa%C3%A7%C3%A3o_din%C3%A2mica
Espero ter ajudado.