Questão para a Prova Oral 057

Semana: 10/03/2003 a 14/03/2003
Assunto: Heapsort e Quicksort

O procedimento BUILD-MAX-HEAP empregado no algoritmo heapsort com heap máximo efetua O(n) chamadas ao procedimento MAX-HEAPIFY, o qual custa O(lg n). Logo, um limite assintótico superior é O(n lg n). Porém, pode-se definir um limite assintótico superior mais restrito para o BUILD-MAX-HEAP com custo de tempo

a) O(lg n), pois entre O(n) e O(lg n), O(lg n) é mais restrito
b) O(lg n), pois a árvore possui altura |_ lg n _|
c) O(n), pois O(n) cresce mais rapidamente do que O(lg n)
d) O(n), pois MAX-HEAPIFY varia de acordo com a altura do nó da árvore e as alturas da maioria dos nós são pequenas
e) NDA

P.S.: |_ lg n _| significa piso de lg n.

Autor: Augusto Jun Devegili
RA: 25620