Artigo original: Divide and Conquer Algorithm Meaning: Explained with Examples
O que são os algoritmos de Dividir para Conquistar?
Dividir para conquistar é um paradigma algorítmico semelhante ao paradigma Greedy (ou "ambicioso") e ao paradigma da Programação Dinâmica. Um algoritmo de dividir para conquistar típico resolve um problema usando os passos a seguir.
- Dividir: quebrar o problema em subproblemas do mesmo tipo. Esse passo envolve a divisão de um problema em subproblemas menores. Os subproblemas devem representar uma parte do problema original. Esse passo geralmente assume uma abordagem recursiva para dividir o problema até que nenhum subproblema possa ser dividido ainda mais. Nesse estágio, subproblemas se tornam atômicos por natureza, mas ainda representam alguma parte do problema em questão.
- Conquistar: resolver recursivamente esses subproblemas. Esse passo recebe vários subproblemas menores para serem resolvidos. Em geral, nesse nível, os problemas são considerados "resolvidos" por eles mesmos.
- Combinar: combinar adequadamente as respostas. Quando os subproblemas menores são resolvidos, esse estágio os combina recursivamente até que eles formulem uma solução para o problema original. Essa abordagem algorítmica funciona recursivamente e os passos de conquistar e unir ficam tão próximos que parecem ser apenas um.
Esse método geralmente permite que haja uma grande redução na complexidade de tempo.
Por exemplo, a Bubble Sort (ordenação de "bolha") usa uma complexidade de O(n^2), enquanto o quicksort (ordenação rápida, uma aplicação do tipo Dividir para Conquistar) reduz a complexidade de tempo para O(nlog(n)). A busca linear tem complexidade de tempo de O(n), enquanto a busca binária (uma aplicação do tipo Dividir para Conquistar) reduz a complexidade de tempo para O(log(n)).
A seguir, vemos alguns algoritmos padrão que são do tipo Dividir para Conquistar.
A busca binária (em inglês, Binary Search)é um algoritmo de pesquisa. Em cada etapa, o algoritmo compara o elemento de entrada (x) com o valor do elemento do meio em um array. Se o valor corresponder, retorna-se o índice do meio. Do contrário, se x for menor que o elemento do meio, o algoritmo faz a recursão para percorrer o lado à esquerda do elemento do meio. Se for maior, faz a recursão para percorrer o lado à direita do elemento do meio.
A ordenação rápida (em inglês, Quick Sort) é um algoritmo de ordenação. O algoritmo seleciona um elemento pivô, reorganiza os elementos do array de tal maneira que todos os elementos menores que o elemento de pivô selecionado sejam movidos para a esquerda do pivô, enquanto todos os elementos maiores que o elemento de pivô selecionado sejam movidos para a direita dele. Por fim, o algoritmo recursivamente ordena os subarrays à esquerda e à direita do elemento de pivô.
A ordenação por mistura (em inglês, Merge Sort) também é um algoritmo de ordenação. O algoritmo divide o array em duas metades, as ordena recursivamente e, finamente, mistura as duas metades ordenadas. A complexidade de tempo desse algoritmo é de O(nLogn) no melhor caso, no caso médio ou no pior caso. Sua complexidade de tempo pode ser entendida facilmente do fato de que a recorrência/recursão tem como equação: T(n) = 2T(n/2) + n.
O par de pontos mais próximos: o problema é encontrar o par de pontos mais próximo em um conjunto de pontos em um plano x-y (ou cartesiano). O problema pode ser resolvido com uma complexidade de tempo de O(n^2) calculando as distâncias de cada par de pontos e comparando as distâncias para encontrar a distância menor. O algoritmo de Dividir para Conquistar resolve o problema em tempo de O(nLogn).
O algoritmo de Strassen é um algoritmo eficaz para a multiplicação de duas matrizes. Um método simples para multiplicar duas matrizes precisa de 3 laços aninhados e tem como complexidade de tempo O(n^3). O algoritmo de Strassen multiplica duas matrizes com complexidade de tempo de O(n^2.8974).
O algoritmo de transformada rápida de Fourier (FFT), de Cooley–Tukey é o algoritmo mais comum para a FFT. Ele é um algoritmo de dividir para conquistar que funciona com complexidade de tempo de O(nlogn).
O algoritmo de Karatsuba foi o primeiro algoritmo de multiplicação assintoticamente mais rápido que o algoritmo quadrático padrão. Ele reduz a multiplicação de dois números de n algarismos a, no máximo, n^1,585 (que é uma aproximação do log de 3 na base 2) produtos de um único algarismo. Ele é, portanto, mais rápido do que o algoritmo clássico, que exige n^2 produtos de um único algarismo.
Dividir para conquistar x Programação dinâmica
Os dois paradigmas dividem o problema em questão em subproblemas e resolvem os subproblemas. Como selecionar um dos paradigmas para determinado problema? Dividir para conquistar deve ser usado quando os mesmos subproblemas não são avaliados várias vezes. Do contrário, deve-se usar a programação dinâmica ou a memoização.
Por exemplo, a busca binária é um algoritmo de dividir para conquistar. Nele, jamais avaliamos os mesmos subproblemas novamente. Por outro lado, para calcular o n-ésimo número de Fibonacci, deve-se preferir a programação dinâmica.