MO417- Complexidade de Algoritmos I
Aula de 14/03/2003
Ata da Resolução de Exercícios
Livro Texto: ALGORITMOS - Teoria e Prática Capítulo 2 - Conceitos Básicos Redator: Éric Hainer Ostroski Questões:6.4-3 ; 6.5-7
Questão 6.4-3
Qual é o tempo de execução de heapsort sobre um arranjo
A de comprimento n que já está ordenado em ordem crescente?
E em ordem decrescente?
Solução:
5
4
3
2
1
=> BUILD-MAXHEAPFY gasta O(n)
1
4
3
2
5
Agora será preciso fazer o HEAP do restante.
=> gastar lg(n)
Assim sendo, vai se gastar no total O(n lg n)
Questão 6.5-7
A operação HEAP-DELETE(A,i) elimina o item do
nó i do heap A. Forneça uma implementação
de HEAP-DELETE que seja executada no tempo O(lg n) para um heap máximo
de n elementos