Questão de Algoritmos e Estrutura de Dados — Algoritmos — CEPS-UFPA 2022
Algoritmos e Estrutura de Dados›Algoritmos
Código
gp036807
Banca
CEPS-UFPA
Órgão
UFPA
Ano
2022
Cargo
CEPS - - Analista de Tecnologia da Informação / Área: Desenvolvimento
Seja V um vetor de n números inteiros distintos. Sobre a complexidade temporal de algoritmos paraordenar V em ordem crescente, é correto afirmar que
Ao algoritmo de ordenação bolha (ou bubblesort) entrega uma complexidade O(n) para qualquerordenação inicial de V.
Bo algoritmo de ordenação por inserção tem complexidade no pior caso O(n), que ocorre quando Vestá inicialmente em ordem decrescente.
Co melhor caso do algoritmo de ordenação rápida (ou quicksort) ocorre quando, a cada sorteio, amediana de um vetor é escolhida como pivô.
Da complexidade no pior caso do algoritmo de ordenação por intercalação (ou mergesort) é O(n log n)e a complexidade no melhor caso, que ocorre quando V está inicialmente em ordem crescente, éO(n).
Eo algoritmo de ordenação por monte (ou heapsort) entrega uma complexidade O(log n) no pior casoe no caso médio.
Revelar gabarito e comentário▾
GabaritoC — o melhor caso do algoritmo de ordenação rápida (ou quicksort) ocorre quando, a cada sorteio, a
mediana de um vetor é escolhida como pivô.
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 de Algoritmos de Ordenação
Gabarito: letra C. A única afirmativa correta é a que descreve o melhor caso do Quicksort: escolher a mediana como pivô a cada etapa garante partições balanceadas e complexidade O(n log n). As demais alternativas erram ao afirmar complexidades lineares para algoritmos que têm pior caso quadrático ou ao confundir as complexidades do Mergesort e Heapsort.
A banca testa o conhecimento das complexidades típicas dos algoritmos clássicos. Vamos analisar cada alternativa:
Algoritmo
Melhor Caso
Pior Caso
Caso Médio
Afirmativa da Alternativa
Correção
Bubblesort
O(n) (vetor ordenado, com otimização)
O(n²)
O(n²)
O(n) para qualquer ordenação inicial (A)
❌ Falsa: pior caso é O(n²)
Insertion sort
O(n) (vetor ordenado)
O(n²) (vetor decrescente)
O(n²)
O(n) no pior caso (B)
❌ Falsa: pior caso é O(n²)
Quicksort
O(n log n) (pivô mediano, partições balanceadas)
O(n²) (pivô extremo)
O(n log n)
Melhor caso com mediana como pivô (C)
✅ Correta
Mergesort
O(n log n)
O(n log n)
O(n log n)
Pior caso O(n log n) e melhor caso O(n) (D)
❌ Falsa: melhor caso também é O(n log n)
Heapsort
O(n log n)
O(n log n)
O(n log n)
O(log n) no pior caso e caso médio (E)
❌ Falsa: complexidade é O(n log n)
Alternativa A — ❌ Incorreta
O Bubblesort tem complexidade O(n) no melhor caso (vetor já ordenado com otimização), mas no pior caso e no caso médio é O(n²). A alternativa afirma que é O(n) "para qualquer ordenação inicial", o que é falso.
Alternativa B — ❌ Incorreta
A ordenação por inserção tem complexidade O(n²) no pior caso, que ocorre justamente quando o vetor está em ordem decrescente (cada elemento precisa ser inserido no início). A alternativa erroneamente diz O(n).
Alternativa C — ✅ Correta ⟵ GABARITO
O melhor caso do Quicksort ocorre quando as partições são equilibradas, ou seja, cada pivô divide o vetor ao meio. Isso é obtido ao escolher a mediana como pivô, resultando em complexidade O(n log n). A alternativa descreve exatamente essa situação.
Alternativa D — ❌ Incorreta
O Mergesort tem complexidade O(n log n) em todos os casos (melhor, pior e médio). A alternativa acerta o pior caso, mas erra ao afirmar que o melhor caso (vetor em ordem crescente) é O(n). Mesmo nessa situação, o algoritmo executa todas as divisões e intercalações, mantendo O(n log n).
Alternativa E — ❌ Incorreta
O Heapsort tem complexidade O(n log n) no pior caso e no caso médio, e também no melhor caso. A alternativa afirma O(log n), que é a complexidade de cada operação de extração, mas o algoritmo realiza n extrações, resultando em O(n log n).
NÃO CAIA NESSA!
A alternativa D é a mais enganosa: muitos candidatos pensam que um vetor já ordenado reduz a complexidade do Mergesort para linear, mas isso é verdade apenas para algoritmos como Insertion sort ou Bubblesort com otimização. O Mergesort sempre divide e intercala independentemente da ordem.