Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM4 Paradigmas de Resolução de Problemas, Dividir e Conquistar, Comparando…
-
Dividir e Conquistar
Exemplos comuns:
- Merge Sort → divide e une listas ordenadas
- Quick Sort → usa um pivô e particiona o conjunto
- Binary Search → reduz o espaço de busca pela metade
- FFT → acelera multiplicações polinomiais
Conceito:
- Quebrar o problema em partes menores
- Resolver cada parte separadamente
- Juntar as soluções parciais para formar a resposta final
Quando aplicar:
- Quando o problema é naturalmente divisível em subpartes independentes
- Quando é possível combinar facilmente os resultados
Pontos fortes:
- Muito eficiente para grandes volumes de dados
- Boa escalabilidade e paralelização
-
-
Comparando
-
Guloso (Greedy):
- Escolhe o melhor passo local
- Simples e rápido, mas exige prova de corretude
Divisão e Conquista:
- Divide o problema em partes recursivas
- Excelente para algoritmos de ordenação e busca
Programação Dinâmica:
- Armazena subresultados para evitar recomputações
- Ideal para otimização e contagem de caminhos
-