Divisão e conquista
Metáfora e Motivação
O projeto de muitos algoritmos eficientes é baseado no método da divisão e conquista. Esse método (ou estratégia de projeto de algoritmos) consiste no seguinte:
Etapas
Dividir
Dividir o problema em uma ou mais subproblemas
Conquistar
Resolver os subproblemas caso esses sejam suficientemente pequenos, caso contrário continuar a divisão
Combinar
Soluções dos subproblemas para a solução do problema original
Vantagens
- Eficiência do algoritmo
- Tratamento da complexidade
- Paralelismo
- Acesso à memória
Processo
- a instância dada do problema é dividida em duas ou mais instâncias menores,
- cada instância menor é resolvida usando o próprio algoritmo que está sendo definido,
- as soluções das instâncias menores são combinadas para produzir uma solução da instância original.
A segunda fase é implementada por uma chamada recursiva. Essa é a fase da conquista.
O método da divisão e conquista produz um algoritmo eficiente se a fase de divisão e a fase da combinação forem suficientemente rápidos.
Exemplos Clássicos de Divisão e Conquista
algoritmo Altura
Um para o problema do segmento de soma máxima.
Busca binária
Divide a instância em duas menores e resolve uma delas; a fase de combinação é vazia.
Mergesort
Divide a instância em duas menores (essa fase é muito rápida) e resolve as duas instâncias menores; a fase de combinação é a que consome mais tempo.
Quicksort
A fase da divisão é lenta e produz duas instâncias menores; a fase de combinação é muito rápida.
Algoritmo da mediana
A fase da divisão, que produz duas instâncias menores, é lenta; a fase da conquista resolve uma dessas instâncias; a fase de combinação é muito rápida.
Algoritmo de Karatsuba
A fase da divisão é muito rápida e produz três instâncias menores; a fase de combinação consiste em algumas operações aritméticas.
Par de pontos mais próximos
Menor distância entre 2 pontos.
Exercício Prático Guiado
- Releia os textos de Busca Binária e MergeSort.
- Para cada um deles, identifique claramente as fases:
- Dividir.
- Conquistar (chamadas recursivas).
- Combinar.
- Escreva a recorrência de tempo correspondente e diga, em uma frase, por que a solução é melhor que a abordagem ingênua.