Divide and Conquer

O paradigma de dividir para conquistar é a base de vários algoritmos conhecidos. Já visitámos a pesquisa binária que é um exemplo clássico, mas outros algoritmos conhecidos que seguem este método são o quicksort e o mergesort. A ideia, como o próprio nome indica, é dividir um problema em problemas mais pequenos, resolver cada um e depois juntar as respostas.

Descrição geral do método

Vejamos alguns artigos que incluem vários exemplos e que explicam mais detalhadamente o método.

Podem ver uma outra descrição do método na respetiva página da Wikipedia:

Aplicações

Iremos ver duas aplicações conhecidas (além das já faladas) e posteriormente vamos abordar alguns problemas.

Closest pair

O primeiro exemplo é o problema do par mais próximo, que, como o nome indica, dado um conjunto de $N$ pontos, pergunta qual o par de pontos que se encontra mais próximo usando uma distância euclidiana. A solução trivial seria $O(N^2)$, mas é possível fazê-lo em $O(N\log(N))$.

Inversões de uma lista

Aqui iremos ver um método semelhante ao mergesort. O problema pede para, dada uma lista $L$, contar o número de pares de elementos da lista que estão fora de ordem (crescente), ou seja, dados os seus índices $i$ e $j$, onde $i < j$, o valor do primeiro é maior que o do segundo, ou seja, $L[i] > L[j]$.

* Skyline problem

Um outro exemplo é o problema da área da skyline de um conjunto de edifícios. Este problema pode ser resolvido de diferentes formas, mas uma delas é baseada em Divide and Conquer.

Outros exemplos

Finalmente, vejamos alguns problemas diferentes.