O algoritmo Heapsort, quando usado para ordenar uma coleção ...

A alternativa correta é a D - O(n log n) e O(n log n).

Vamos agora entender o tema da questão e discutir as alternativas.

O Heapsort é um algoritmo de ordenação baseado na estrutura de dados Heap, especificamente um Max-Heap (ou Min-Heap, dependendo da ordem de classificação desejada). Ele funciona em duas principais fases: a construção do heap e a ordenação propriamente dita, extraindo elementos do heap.

Para resolver esta questão, é necessário conhecer a complexidade de tempo do Heapsort em diferentes casos. A complexidade de tempo de um algoritmo é frequentemente expressa usando a notação Big-O, que descreve o comportamento do tempo de execução em função do tamanho da entrada n.

Heapsort possui a seguinte complexidade de tempo:

• Melhor caso: O(n log n)
• Pior caso: O(n log n)

Vamos justificar por que a alternativa D é correta e as outras alternativas não são.

Alternativa D: O(n log n) e O(n log n)

Esta é a alternativa correta, pois, independentemente da configuração inicial dos elementos (melhor ou pior caso), o Heapsort sempre realiza a construção do heap, que é O(n), seguida por n operações de extração e reajuste do heap, cada uma com complexidade O(log n). Portanto, o tempo total é O(n log n) tanto no melhor caso quanto no pior caso.

Alternativa A: O(1) e O(n log n)

Esta alternativa está incorreta. A construção do heap e a ordenação subsequente não podem ser feitas em tempo constante O(1). O tempo de execução mínimo é O(n log n) devido às operações necessárias para manter a propriedade de heap.

Alternativa B: O(n²) e O(n⁴)

Esta alternativa também está incorreta. Heapsort nunca atinge uma complexidade de tempo tão alta quanto O(n²) ou O(n⁴). Esses tempos de execução são muito maiores do que o real comportamento do Heapsort.

Alternativa C: O(n) e O(n²)

Esta alternativa está incorreta. Como mencionado anteriormente, a construção do heap é O(n), mas a ordenação subsequente não pode ser feita em O(n) no melhor caso, nem atinge O(n²) no pior caso. A complexidade correta é O(n log n).

Alternativa E: O(n log n) e O(n log n⁴)

Esta alternativa também está incorreta. A complexidade do pior caso não é O(n log n⁴), mas sim O(n log n). A notação O(n log n⁴) é incorreta e desnecessária, pois log n⁴ é simplesmente 4 log n, o que não altera a ordem de complexidade.

Espero que esta explicação tenha esclarecido suas dúvidas sobre a complexidade de tempo do Heapsort e como identificar a alternativa correta em questões de concursos públicos.

d) O(n log n) e O(n log n) 

Veja no link  abaixo um  quadro interessante da complexidade dos algoritmos

https://www.ft.unicamp.br/liag/siteEd/definicao/ordenacao.php

Gabarito D

Comparações no pior caso: 2n log2n + O(n) é o mesmo que 2n lgn + O(n)

Trocas no pior caso: n log2n + O(n) é o mesmo que n lgn + O(n)

Melhor e pior caso: O(n log2n) é o mesmo que O(n lgn)

"Retroceder Nunca Render-se Jamais !"
Força e Fé !
Fortuna Audaces Sequitur !

Força Guerreiro!!!!!!

HEAPSORT ele é todo O(n log n)

- Melhor Caso = O(n log n)

- Caso Médio = O(n log n)

- Pior Caso = O(n log n)

GAB D.