DIVISÃO & CONQUISTA

DIVISÃO & CONQUISTA

1. O que é?

   • Técnica que divide um problema grande em partes menores e independentes, resolve cada parte e combina os resultados para resolver o problema original

2. Características / Vantagens

   • - Reduz problemas grandes em partes menores e mais fáceis; Explora recursão naturalmente; Pode melhorar o desempenho (em relação a soluções ingenuas; Facilita paralelização; Base de muitos algoritmos eficientes

3. Recorrência do Merge Sort

   • Para um array de tamanho n:
     • T(n) = 27(n/2) + n
       • 2T(/2): divide em 2 subproblemas de tamano n/2; + n: custo para combinar (intercalar)
         • SOLUÇÃO: T(n) = Theta(n log n)

4. Estratégia algorítmica que resolve um problema dividindo-o em subproblemas menores do mesmo tipo, resolvendo-os recursivamente e combinando as soluções para obter a solução final

   • APLICAÇÕES
     • Busca binária; Merge sort; Quick sort; e muitos outros...

5. COMO FUNCIONA

   • DIVIDIR
     • Quebrar o problema em subproblemas menores: subarranjos.
   • CONQUISTAR
     • Resolve cada subproblema recursivamente.
   • COMBINAR
     • Combina as soluções dos subproblemas para forma a solução final.

6. EXEMPLO: MERGE SORT

   • 1- DIVIDIR: divide o array até chegar a subarranjos com 1 elemento.
   • 2 - CONQUISTAR: Cada subarranjo de 1 elemento já está ordenado.
   • 3 - COMBINAR: Intercala (merge) os subarranjos ordenados até formar o array final ordenado.

Images and files in the map