Questão de Algoritmos e Estrutura de Dados — Algoritmos — IDECAN 2019
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq500348
Banca
IDECAN
Órgão
IF-PB
Ano
2019
Nível
Superior
Cargo
Professor - Informática
O Quick-Sort é considerado o algoritmo de ordenação baseado em comparação mais eficiente, mas em alguns casos sua complexidade é igual ao do Bubble-Sort. Assinale a alternativa que indica a complexidade do Quick-Sort quando o vetor está ordenado em ordem decrescente:
AO(n)
BO(n^2 log n)
CO(n log n)
DO(n^2)
EO(log n)
Revelar gabarito e comentário▾
GabaritoD — O(n^2)
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”.
Análise de complexidade do QuickSort em vetor decrescente
Gabarito: letra D — O(n²). Quando o vetor está em ordem decrescente e a escolha do pivô é ingênua (ex.: primeiro elemento), o QuickSort atinge seu pior caso, com complexidade O(n²), mesma do BubbleSort, conforme o enunciado menciona.
A banca testa o conhecimento do comportamento do QuickSort em diferentes cenários. O caso médio e melhor do QuickSort é O(n log n), mas o pior caso ocorre quando o pivô é sempre o menor ou maior elemento, gerando partições desbalanceadas — exatamente o que acontece com vetor já ordenado ou inversamente ordenado (decrescente).
1Pivô ingênuo (1º elemento)
2Partição desbalanceada
3n chamadas recursivas
4Custo O(n) por chamada
5Complexidade O(n²)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O(n) é complexidade linear, incompatível com o pior caso do QuickSort. Essa complexidade ocorreria, por exemplo, em algoritmos como a busca linear.
Alternativa B — ❌ Incorreta
O(n² log n) não é comum na análise de algoritmos de ordenação. O termo logarítmico não se aplica ao pior caso do QuickSort.
Alternativa C — ❌ Incorreta
O(n log n) é a complexidade do caso médio e do melhor caso (quando o pivô divide o vetor ao meio). Não é a do pior caso com vetor decrescente.
Alternativa D — ✅ Correta ⟵ GABARITO
O pior caso do QuickSort é O(n²). Com vetor decrescente e pivô fixo no primeiro elemento, cada partição separa apenas um elemento, resultando em n chamadas recursivas com custo linear cada.
Alternativa E — ❌ Incorreta
O(log n) é complexidade logarítmica, típica de busca binária, não de ordenação.
NÃO CAIA NESSA!
A banca explora a confusão entre o caso médio (n log n) e o pior caso (n²). Muitos alunos lembram que QuickSort é “rápido” e marcam n log n, mas esquecem que em entradas ordenadas/inversamente ordenadas o desempenho piora drasticamente se o pivô não for bem escolhido. Na prova, desconfie sempre de perguntas sobre vetor já ordenado com QuickSort – a resposta quase sempre é O(n²).