Algoritmos de divisão e conquista

Os dois algoritmos de organização que vimos até agora, seleção sort e inserção sort, tem o pior dos tempos de $\mathrm{\Theta }(n^2)$‍. Quando o tamanho da matriz de entrada é grande, esses algoritmos podem levar bastante tempo para executar. Nesse e no próximo tutorial, nós veremos outros dois algoritmos de organização, merge sort e quicksort, os quais os tempos de execução são melhores. Em particular, merge sort executará em $\mathrm{\Theta }(n\lg n)$‍ de tempo todas as vezes, e o quicksort executará em in $\mathrm{\Theta }(n\lg n)$‍ de tempo no melhor caso em média, mesmo assim o tempo do seu pior caso é $\mathrm{\Theta }(n^2)$‍. Aqui está uma tabela com os quatro algoritmos e seus tempos de execução:

Ambos merge sort e quicksort empregam um paradigma de algoritmo comum baseado na recursão. Esse paradigma, dividir-e-conquistar, quebra o problema em subproblemas que são similares ao problema orgininal, recursivamente resolve os subproblemas, e finalmente combina as soluções para resolver o problema original. Porque dividir e conquistar resolve subproblemas recursivamnete, cada subproblema deve ser menor que o problema original, e deve existir um problema base para os subproblemas. Você deve pensar o algoritmo dividir-e-conquistar como tendo três partes:

Você pode facilmente lembrar dos passos do algoritmo de dividir-e-conquistar como sendo dividir, conquistar, combinar. Aqui está como visualizar um passo, assumindo que cada passo de dividir cria dois subproblemas (alguns algoritmos de dividir-e-conquistar criam mais de dois):

Se expandirmos mais duas etapas recursivas, ele terá esta aparência:

Como dividir-e-conquistar cria pelo menos dois subproblemas, um algoritmo de dividir-e-conquistar faz múltiplas chamadas recursivas.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.