Questão de Algoritmos e Estrutura de Dados — Algoritmos — IV - UFG 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq863036
Banca
IV - UFG
Órgão
UFT
Ano
2023
Nível
Superior
Cargo
CS-UFG - - Analista de Tecnologia da Informação
A complexidade de algoritmos refere-se à análise e à avaliação de desempenho de um algoritmo no que se diz respeito aos recursos computacionais necessários para se resolver determinado problema. O tempo de execução do algoritmo Heapsort é
AO(n²).
BO(log n).
CO(n³).
DO(n log n).
Revelar gabarito e comentário▾
GabaritoD — O(n log n).
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Complexidade do Heapsort
Gabarito: letra D. O algoritmo Heapsort possui complexidade de tempo O(n log n) no pior caso, no melhor caso e no caso médio. Essa característica o torna um algoritmo de ordenação eficiente e estável em termos de desempenho assintótico.
A questão cobra o conhecimento da notação Big-O para algoritmos clássicos de ordenação. O Heapsort constrói uma max-heap (ou min-heap) e então extrai sucessivamente o maior (ou menor) elemento, realizando operações de heapify que custam O(log n) cada, totalizando O(n log n).
Alternativa A — ❌ Incorreta
O(n²) é a complexidade de algoritmos quadráticos como Bubble Sort, Insertion Sort e Selection Sort. O Heapsort é significativamente mais eficiente para grandes entradas.
Alternativa B — ❌ Incorreta
O(log n) é complexidade logarítmica, típica de busca binária em uma estrutura ordenada. Nenhum algoritmo de ordenação baseado em comparação pode ter complexidade inferior a O(n log n) no pior caso; O(log n) seria impossível.
Alternativa C — ❌ Incorreta
O(n³) é cúbico, encontrado em algoritmos muito ineficientes ou em operações matriciais ingênuas. O Heapsort é muito mais rápido.
Alternativa D — ✅ Correta ⟵ GABARITO
O Heapsort executa em tempo O(n log n). É um algoritmo de ordenação por comparação que utiliza uma estrutura de dados heap binário. Exemplos: construir o heap custa O(n) e cada extração custa O(log n), para n extrações totalizando O(n log n).
PEGA ESSA DICA!
Decore as complexidades dos principais algoritmos de ordenação: