Se você está vendo esta mensagem, significa que estamos tendo problemas para carregar recursos externos em nosso website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

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 Θ(n2). 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 Θ(nlgn) de tempo todas as vezes, e o quicksort executará em in Θ(nlgn) de tempo no melhor caso em média, mesmo assim o tempo do seu pior caso é Θ(n2). 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)Θ(n2)Θ(n2)Θ(n2)
Insertion sortΘ(n2)Θ(n)Θ(n2)
Ordenação por combinação (merge sort)Θ(nlgn)Θ(nlgn)Θ(nlgn)
QuicksortΘ(n2)Θ(nlgn)Θ(nlgn)

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.