Algoritmos: Complexidade, Divisão e Conquista e Guloso

Mostre a complexidade pessimista do algoritmo do QuickSort

Pior caso: pode chegar a O(n²); esta variação ocorre em função da escolha do pivô inicial.

Pior caso do Quicksort: Sequências ordenadas ou quase ordenadas.

O tempo do Quicksort ainda será O(n²) no pior caso, porque existe a chance de que o pivô seja o menor elemento na sequência.

Explique a técnica PMA da divisão e conquista

É um PMA (Paradigma de Projeto de Algoritmos) caracterizado por decomposições e recombinações. Dado um problema, ele é decomposto em subproblemas menores. Se o tamanho dos subproblemas é relativamente grande, com soluções não imediatas, o processo é aplicado novamente, até que se obtenham subproblemas tão pequenos que possam ser resolvidos facilmente.

• Sucessivas decomposições: são expressas por recursão.
• Divisão: Dividir o problema original, de tamanho n, em a problemas menores (subproblemas), em geral, do mesmo tamanho.
• Conquista: Resolver cada subproblema recursivamente.
• Combinação: Combinar as soluções encontradas, compondo uma solução para o problema original.

Explique quando se deve utilizar a programação dinâmica ao invés da divisão e conquista

Quando a estratégia de divisão e conquista gera um grande número de subproblemas idênticos, a recursão se torna muito cara. Nesse caso, é melhor armazenar as soluções desses subproblemas em uma tabela. Isso caracteriza a programação dinâmica.

Explique a técnica PMA do algoritmo guloso

Elementos da estratégia gulosa:

A partir de uma sequência de escolhas, um algoritmo guloso busca encontrar a solução ótima para o problema em questão. A estratégia utilizada em cada passo é escolher a solução que parece ser a melhor. No entanto, nem sempre um algoritmo guloso consegue resolver um problema de otimização. Mas existem duas características que podem indicar que os problemas podem ser resolvidos utilizando uma estratégia gulosa:

• Escolha gulosa: Uma solução globalmente ótima pode ser alcançada fazendo-se uma escolha localmente ótima (gulosa), isto é, aquela que parece ser a melhor naquele momento, desconsiderando-se resultados de subproblemas.

É importante ressaltar a necessidade de se provar que realmente uma escolha gulosa em cada um dos passos irá levar a uma solução ótima global. O que normalmente se faz é examinar uma solução ótima global para algum subproblema e depois mostrar que ela pode ser modificada em uma solução gulosa. Isto irá resultar em um subproblema menor, mas similar. Frequentemente é possível fazer escolhas gulosas de uma forma mais rápida (resultando em algoritmos mais eficientes) se uma estrutura de dados apropriada for utilizada (fila de prioridades, por exemplo), ou então se houver um pré-processamento da entrada.

ENADE “E” OUTRA PERGUNTA “A”