Questão de Algoritmos e Estrutura de Dados — Algoritmos — IV - UFG 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq975348
Banca
IV - UFG
Órgão
UFCAT
Ano
2023
Nível
Superior
Cargo
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 Heapsort utiliza uma estrutura de heap para ordenar, realizando operações de inserção e remoção que custam O(log n) cada, repetidas n vezes, resultando em complexidade O(n log n) no pior caso, no melhor caso e no caso médio. É um dos algoritmos de ordenação eficientes, junto com Mergesort e Quicksort (embora este último tenha pior caso O(n²)).
A banca testa o conhecimento das complexidades clássicas dos algoritmos de ordenação.
Alternativa A — ❌ Incorreta
O(n²) é a complexidade de algoritmos elementares como Bubble Sort, Insertion Sort e Selection Sort. O Heapsort é mais eficiente, garantindo O(n log n).
Alternativa B — ❌ Incorreta
O(log n) é a complexidade de algoritmos como busca binária, não de ordenação. Uma ordenação completa exige, no mínimo, examinar todos os elementos, logo a complexidade é pelo menos linear.
Alternativa C — ❌ Incorreta
O(n³) é típico de algoritmos como multiplicação ingênua de matrizes ou alguns algoritmos de programação dinâmica. Não se aplica ao Heapsort.
Alternativa D — ✅ Correta ⟵ GABARITO
O Heapsort possui complexidade O(n log n) no pior caso, pois:
A construção do heap é O(n).
Cada uma das n remoções do maior elemento custa O(log n) para restaurar a propriedade de heap.
Totalizando O(n log n). É um algoritmo de ordenação estável? Não, mas esse não é o foco.
PEGA ESSA DICA!
Memorize as complexidades dos principais algoritmos de ordenação:
Algoritmo
Pior caso
Melhor caso
Caso médio
Bubble Sort
O(n²)
O(n)
O(n²)
Insertion Sort
O(n²)
O(n)
O(n²)
Selection Sort
O(n²)
O(n²)
O(n²)
Merge Sort
O(n log n)
O(n log n)
O(n log n)
Heap Sort
O(n log n)
O(n log n)
O(n log n)
Quick Sort
O(n²)
O(n log n)
O(n log n)
Destaque para o Heapsort, que garante O(n log n) mesmo no pior caso.