MO417 - Questão para a prova oral

Número: 047

Enunciado:
Considere o seguinte algoritmo para encontrar o máximo valor em um conjunto A com n valores. O algoritmo percorre os elementos do conjunto dois a dois, descobrindo o máximo entre os pares e formando um novo A' com os máximos. Após a primeira iteração, o conjunto de busca reduz-se a teto(n/2) (a função teto retona o valor arredondado para cima). Se a seleção do maior aos pares for realizada iterativamente, diminuido o problema pela metade a cada iteração, no final o conjunto de busca terá apenas um elemento, que será o valor máximo dentre os n valores iniciais. Pode-se dizer que:

1. A redução do problema iterativamente torna o algoritmo melhor que todos os algoritmos conhecidos para busca do máximo.
2. O tempo do algoritmo é &Theta(n), mas as constantes envolvidas na notação são menores do que as constantes de outros algoritmos.
3. O algoritmo tem custo &Theta(lg n) devido às reduções nas buscas que ele produz.
4. Este é um algoritmo ruim, pois aumenta o número de comparações necessárias para achar o máximo.
5. NDA

Autor(a): Ricardo Dutra da Silva