Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCC 2017
Algoritmos e Estrutura de Dados›Algoritmos
Código
fc038604
Banca
FCC
Órgão
TRF - 5ª REGIÃO
Ano
2017
Nível
Superior
Cargo
Analista Judiciário - Informática Desenvolvimento
O algoritmo QuickSort usa uma técnica conhecida por divisão e conquista, onde problemas complexos são reduzidos em problemas menores para se tentar chegar a uma solução. A complexidade média deste algoritmo em sua implementação padrão e a complexidade de pior caso são, respectivamente,
AO(n-1) e Ο(n³).
BΟ(n²) e Ο(n log n²).
CO(n²) e O(n³).
DΟ(n) e Ο(n²).
EΟ(n log n) e Ο(n²).
Revelar gabarito e comentário▾
GabaritoE — Ο(n log n) e Ο(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
Gabarito: letra E. A complexidade média do QuickSort em sua implementação padrão é O(n log n), e a complexidade de pior caso é O(n²). O pior caso ocorre quando o pivô escolhido é sempre o maior ou o menor elemento, gerando partições desbalanceadas. As demais alternativas trazem valores incorretos, trocando as ordens ou usando expoentes errados.
1Melhor casoO(n log n)
2Caso médioO(n log n)
3Pior casoO(n²)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma O(n-1) para o caso médio e O(n³) para o pior caso. O(n-1) é linear, não corresponde ao comportamento médio do QuickSort. O pior caso não é cúbico.
Alternativa B — ❌ Incorreta
Inverte os valores: apresenta O(n²) para o caso médio e O(n log n²) para o pior caso. O(n log n²) equivale a O(n * 2 log n) = O(n log n), que seria a complexidade média, não a de pior caso. Além disso, O(n²) não é a média.
Alternativa C — ❌ Incorreta
Afirma O(n²) para o caso médio e O(n³) para o pior caso. A média é O(n log n), não quadrática; o pior caso é O(n²), não cúbico.
Alternativa D — ❌ Incorreta
Apresenta O(n) para o caso médio e O(n²) para o pior caso. O caso médio não é linear.
Alternativa E — ✅ Correta ⟵ GABARITO
A complexidade média do QuickSort é O(n log n), e a de pior caso é O(n²), conforme análise clássica de algoritmos de ordenação baseados em comparação.
PEGA ESSA DICA!
O QuickSort tem pior caso O(n²) quando o pivô é sempre o extremo (lista já ordenada) e a escolha do pivô não é aleatória. Para evitar isso, usam-se estratégias como pivô aleatório ou mediana de três. Decore os três casos: melhor/médio O(n log n) e pior O(n²).