Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
fg077370
Banca
FGV
Órgão
CVM
Ano
2024
Nível
Superior
Cargo
Analista - Perfil 8 - TI / Sistemas e Desenvolvimento - Tarde
O analista Joaquim precisou ordenar um array com N elementos. Para economizar tempo, Joaquim optou por usar um algoritmo já disponível na biblioteca de ordenação. A biblioteca contém as implementações originais dos algoritmos Quicksort, Selection Sort, Insertion Sort, Merge Sort e Heap Sort. O analista escolheu o algoritmo que, no pior caso, apresenta uma relação quadrática entre a quantidade de operações necessárias para a ordenação e o número de elementos do array. No caso médio, a quantidade de operações necessárias se aproxima de N multiplicado por um logaritmo de N.Joaquim escolheu o algoritmo de ordenação:
AQuicksort;
BHeap Sort;
CMerge Sort;
DInsertion Sort;
ESelection Sort.
Revelar gabarito e comentário▾
GabaritoA — Quicksort;
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”.
Algoritmos de ordenação: complexidade
Gabarito: letra A (Quicksort). O Quicksort é o único algoritmo, entre os citados, que apresenta complexidade quadrática O(N²) no pior caso e, no caso médio, complexidade O(N log N), exatamente como descrito no enunciado.
A banca testa o conhecimento das complexidades típicas dos principais algoritmos de ordenação. A chave está em identificar qual deles combina pior caso quadrático com caso médio linearítmico.
NÃO CAIA NESSA!
Muitos candidatos confundem os casos do Insertion Sort e do Selection Sort, que também são O(N²) no pior caso, mas — diferentemente do Quicksort — não apresentam caso médio O(N log N); ambos têm caso médio O(N²). A pegadinha está em ignorar o caso médio e focar apenas no pior caso, o que levaria a múltiplas alternativas aparentemente corretas.
Alternativa A — ✅ Correta ⟵ GABARITO
O Quicksort possui, no pior caso (quando o pivô é sempre o menor ou o maior elemento), complexidade O(N²). Já no caso médio, com escolha aleatória de pivô, a complexidade é O(N log N). Essas características correspondem exatamente ao que Joaquim buscava.
Alternativa B — ❌ Incorreta
O Heap Sort tem complexidade O(N log N) tanto no pior caso quanto no caso médio, nunca quadrática. Portanto, não atende ao requisito de relação quadrática no pior caso.
Alternativa C — ❌ Incorreta
O Merge Sort também possui complexidade O(N log N) em todos os casos (pior, médio e melhor). Não se encaixa na descrição.
Alternativa D — ❌ Incorreta
O Insertion Sort tem pior caso O(N²) e caso médio O(N²), não O(N log N). O caso médio é quadrático, não linearítmico.
Alternativa E — ❌ Incorreta
O Selection Sort, assim como o Insertion Sort, possui pior caso e caso médio O(N²), sem alcançar O(N log N) em nenhuma circunstância.
PEGA ESSA DICA!
Memorize a tabela de complexidades dos principais algoritmos de ordenação. O Quicksort é o único que mistura pior caso quadrático com caso médio O(N log N). O Merge Sort e o Heap Sort são sempre O(N log N); Insertion e Selection são sempre O(N²). Esta é uma das perguntas mais frequentes em concursos sobre complexidade de algoritmos.