Questão de Algoritmos e Estrutura de Dados — Algoritmos — INSTITUTO AOCP 2020
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq603475
Banca
INSTITUTO AOCP
Órgão
Prefeitura de Novo Hamburgo - RS
Ano
2020
Nível
Superior
Cargo
Analista de Desenvolvimento de Sistemas
Assinale a alternativa que apresenta o tempo de execução do pior caso e do melhor caso para o algoritmo quicksort ou ordenação rápida.
APior caso: O(n²); melhor caso: O(n).
BPior caso: O(n lg n); melhor caso: O(n).
CPior caso: O(n); melhor caso: O(n + m).
DPior caso: O(n lg n); melhor caso: O(n + m).
EPior caso: O(n²); melhor caso: O(n lg n).
Revelar gabarito e comentário▾
GabaritoE — Pior caso: O(n²); melhor caso: O(n lg 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”.
QuickSort: Complexidade de Tempo
Gabarito: letra E. O pior caso do quicksort é O(n²) e o melhor caso é O(n log n). Isso ocorre porque, no pior caso, o pivô escolhido é sempre o menor ou maior elemento, gerando partições desbalanceadas (uma de tamanho 0 e outra de n-1), resultando em complexidade quadrática. No melhor caso, o pivô divide o array em duas metades aproximadamente iguais, levando a O(n log n). Essas informações são amplamente documentadas na literatura, como na descrição do algoritmo na Wikipédia.
QuickSort: Pior caso (O(n²), Pivô extremo (menor/maior), Partição desbalanceada (0 e n-1)); Melhor caso (O(n log n), Pivô mediano, Partição equilibrada (metades iguais)); Caso médio (O(n log n))
Alternativa A — ❌ Incorreta
Apresenta melhor caso O(n). O melhor caso do quicksort é O(n log n), não linear. O(n) seria característico de algoritmos como counting sort (não baseado em comparação) ou em situações específicas, mas não no quicksort.
Alternativa B — ❌ Incorreta
Afirma pior caso O(n log n). O pior caso do quicksort é O(n²). O(n log n) é a complexidade do melhor caso e do caso médio, mas não do pior.
Alternativa C — ❌ Incorreta
Apresenta pior caso O(n) e melhor caso O(n+m). Ambos estão incorretos. O(n) é muito otimista para o pior caso, e O(n+m) não é a notação usada para o quicksort (poderia representar a complexidade de algoritmos como bucket sort ou merge sort em listas).
Alternativa D — ❌ Incorreta
Diz pior caso O(n log n) e melhor caso O(n+m). O pior caso está errado (deveria ser O(n²)); o melhor caso também está errado (O(n log n), não O(n+m)).
Alternativa E — ✅ Correta ⟵ GABARITO
Essa alternativa apresenta corretamente a complexidade: pior caso O(n²) e melhor caso O(n log n). Conforme a descrição do quicksort, esses são os limites conhecidos.
Conclusão: A única alternativa que corresponde à complexidade do quicksort é a letra E.