Divisão e conquista

Divisão e conquista

1. Resolve recursivamente o problema quebrando em partes menores

   • *Simplifica problemas complexos
   • Eficiente
   • Paralelismo

2. Dividir, conquistar, combinar

   • divide em subproblemas
   • Conquista - resolve recursivamente
   • Combinar as soluções para resolver o problema principal

3. Merge Sort

4. Busca binária

5. Máximo e mínimo

6. Algoritmo de Savitch

7. Algoritmo genérico DivisãoeConquista(x) if x é pequeno ou simples then return resolver(x) else decompor x em conjuntos menores x0, x1, … xn for i = 0 to n do yi = DivisãoeConquista(xi) combinar yi’s return y