Divisão e Conquista

Divisão e Conquista

1. O paradigma

   • Dividir: Quebrar o problema original em subproblemas menores. (Ex: criar subarranjos).
   • Conquistar: Resolver os subproblemas de forma recursiva até chegarem ao caso base.
   • Combinar: Juntar as soluções dos subproblemas para formar a solução do problema maior.

2. MergeSort

   • Etapa de Divisão: Vetor [70, 30, 50, 10] é quebrado em subarranjos menores: [70, 30] e [50, 10], até chegar em elementos únicos [70], [30], [50], [10].
   • Etapa de Combinação (Merge): Junta e ordena: [30, 70] e [10, 80] -> [10, 30, 70, 80].
   • Uso de Relações de Recorrência para calcular o tempo de execução.
     • Ex: T(n) = 2T(n/2) + Θ(n) para o MergeSort.

Bilder und Dateien der Mindmap