Conteúdo principal
Ciência da Computação
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:
| Algoritmo | Tempo de execução no pior caso | Tempo de execução no melhor caso | Tempo 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:
- Dividir o problema em um número de subproblemas que sejam partes menores do mesmo problemas.
- Conquistar os subproblemas resolvendo-os recursivamente. Se eles forem pequenos o suficiente, resolva os subproblemas como problemas base.
- 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.