If you're seeing this message, it means we're having trouble loading external resources on our website.

Se você está atrás de um filtro da Web, certifique-se que os domínios *.kastatic.org e *.kasandbox.org estão desbloqueados.

Conteúdo principal

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 \Theta, left parenthesis, n, squared, right parenthesis. 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 \Theta, left parenthesis, n, \lg, n, right parenthesis de tempo todas as vezes, e o quicksort executará em in \Theta, left parenthesis, n, \lg, n, right parenthesis de tempo no melhor caso em média, mesmo assim o tempo do seu pior caso é \Theta, left parenthesis, n, squared, right parenthesis. Aqui está uma tabela com os quatro algoritmos e seus tempos de execução:
AlgoritmoTempo de execução no pior casoTempo de execução no melhor casoTempo de execução médio
ordenação por seleção (selection sort)\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis
Insertion sort\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, right parenthesis\Theta, left parenthesis, n, squared, right parenthesis
Ordenação por combinação (merge sort)\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis
Quicksort\Theta, left parenthesis, n, squared, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis\Theta, left parenthesis, n, \lg, n, right parenthesis

dividir e conquistar

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:
  1. Dividir o problema em um número de subproblemas que sejam partes menores do mesmo problemas.
  2. Conquistar os subproblemas resolvendo-os recursivamente. Se eles forem pequenos o suficiente, resolva os subproblemas como problemas base.
  3. Combinar as soluções dos subproblemas em uma solução para o problema original.
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.

Quer participar da conversa?

Nenhuma postagem por enquanto.
Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.