Questão de Algoritmos e Estrutura de Dados — Algoritmos — SUGEP - UFRPE 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq556131
Banca
SUGEP - UFRPE
Órgão
UFRPE
Ano
2019
Nível
Médio
Os algoritmos de ordenação são utilizados para os mais diversos cenários de dados. Apesar de terem o mesmo objetivo (ordenação), possuem diferentes complexidades em relação ao número (n) de elementos a serem ordenados. O “quiksort” se destaca como um dos algoritmos mais rápidos para ordenação. No pior caso, a complexidade “quicksort” será:
AO(logn)
BO(n logn)
CO(n)
DO(n²)
EO(n )
Revelar gabarito e comentário▾
GabaritoD — O(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 Quicksort no Pior Caso
Gabarito: letra D. No pior caso, o algoritmo quicksort apresenta complexidade O(n²), que ocorre quando as partições são altamente desbalanceadas (ex.: pivô sempre o menor ou maior elemento). O caso médio e o melhor caso são O(n log n).
A questão testa o conhecimento das complexidades típicas de algoritmos de ordenação, especialmente o quicksort, que é um dos mais rápidos na prática, mas tem um pior caso quadrático.
Quicksort
1Melhor caso
O(n log n)
2Caso médio
O(n log n)
3Pior caso
O(n²)
Partições desbalanceadas
Pivô sempre menor
Pivô sempre maior
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O(log n) é a complexidade de algoritmos como a busca binária, não do quicksort. O quicksort, mesmo no melhor caso, é O(n log n), nunca logarítmico.
Alternativa B — ❌ Incorreta
O(n log n) é a complexidade do caso médio e do melhor caso do quicksort, mas não do pior caso. É também a complexidade de outros algoritmos como Merge Sort e Heap Sort.
Alternativa C — ❌ Incorreta
O(n) é complexidade linear, típica de algoritmos como busca linear ou ordenação por contagem (em certas condições). O quicksort não possui complexidade linear em nenhum caso.
Alternativa D — ✅ Correta ⟵ GABARITO
No pior caso, o quicksort tem complexidade O(n²). Isso acontece quando a escolha do pivô resulta em partições de tamanho 1 e n-1 repetidamente, levando a n chamadas recursivas com custo linear cada.
Alternativa E — ❌ Incorreta
Repetição da alternativa C (O(n)). Não corresponde ao pior caso do quicksort.
PEGA ESSA DICA!
Decore as complexidades dos principais algoritmos de ordenação. Uma tabela mental ajuda: