MO417 - Questão para a prova oral

Número: 102

Enunciado:

Considere um algoritmo de ordenação baseado no uso de Heaps Binomiais, que funcione da seguinte forma:
- Dado um vetor desordenado A, monta um Heap Binomial com seus elementos;
- Retira o elemento de valor mínimo em A e o insere num vetor de saída B (após o último elemento existente em B);
- Repete o procedimento acima até que todos os elementos estejam no vetor B;
- Retorna o vetor ordenado B.

Quanto a este algoritmo de ordenação, podemos dizer que sua complexidade, no pior caso é de:

1. O(n lg n)
2. O(2 ^{lg n})
3. O(lg²n)
4. O(lg n)
5. NDA

Autor(a): Fernando José Vieira da Silva (RA: 085324)