Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2025
Algoritmos e Estrutura de Dados›Algoritmos
Código
fg107156
Banca
FGV
Órgão
CPRM
Ano
2025
Nível
Superior
Cargo
Analista em Geociências - Análise e Desenvolvimento de Sistemas
A complexidade de caso médio representa o tempo de execução esperado de um algoritmo, considerando a distribuição típica das entradas possíveis para um conjunto de n elementos a serem ordenados.Considerando a análise assintótica, o algoritmo de ordenação que apresenta complexidade de tempo de execução de caso médio O(log (n)n), sendo O(.) a notação em Big-O, é o
Abucket sort com insertion sort (assumindo distribuição uniforme dos elementos).
Bcounting sort.
Cinsertion sort.
Dmerge sort.
Eradix sort.
Revelar gabarito e comentário▾
GabaritoD — merge sort.
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 Ordenação: Caso Médio O(n log n)
Gabarito: letra D – Merge sort. O merge sort é o único algoritmo dentre as alternativas que apresenta complexidade de caso médio Θ(n log n) (ou O(n log n) na notação Big-O). Essa é uma característica clássica dos algoritmos de ordenação por intercalação (merge sort) e também do heap sort, mas não das demais opções.
A questão cobra conhecimento das complexidades assintóticas médias dos principais algoritmos de ordenação. Para resolver, é necessário lembrar que:
Bucket sort (com insertion sort): caso médio O(n) se a distribuição for uniforme e os buckets forem pequenos.
Counting sort: O(n + k), onde k é o intervalo dos valores – linear.
Insertion sort: caso médio O(n²).
Merge sort: caso médio Θ(n log n).
Radix sort: O(d · (n + k)), onde d é o número de dígitos – linear em relação ao tamanho da entrada.
A única alternativa com complexidade O(n log n) é o merge sort.
Alternativa A – ❌ Incorreta
Afirma que o bucket sort (com insertion sort) tem caso médio O(n log n). Na verdade, assumindo distribuição uniforme dos elementos, o bucket sort apresenta caso médio O(n), pois os elementos são distribuídos em baldes que, em média, têm tamanho constante. A inserção em cada balde (com insertion sort) é O(1²) = O(1), e a concatenação é O(n). Portanto, a complexidade média é linear, não O(n log n).
Alternativa B – ❌ Incorreta
O counting sort é um algoritmo de ordenação estável baseado em contagem. Sua complexidade de caso médio é O(n + k), onde k é o intervalo dos valores a serem ordenados. Como geralmente k é da mesma ordem de n, pode-se dizer que é linear – muito inferior a O(n log n) para entradas grandes.
Alternativa C – ❌ Incorreta
O insertion sort tem complexidade de caso médio O(n²), pois, em média, para cada elemento é necessário deslocar aproximadamente metade dos elementos já ordenados. Não atinge O(n log n).
Alternativa D – ✅ Correta
O merge sort é um algoritmo de divisão e conquista que sempre apresenta complexidade Θ(n log n) no caso médio (e também no pior caso). Ele divide recursivamente a lista até ter sublistas de tamanho 1 e depois intercala, realizando O(n) comparações por nível de recursão, totalizando O(n log n).
Alternativa E – ❌ Incorreta
O radix sort ordena processando dígito a dígito (da direita para a esquerda ou vice-versa). Sua complexidade é O(d · (n + k)), onde d é o número de dígitos e k a base. Para inteiros de comprimento fixo, d é constante, resultando em complexidade linear – novamente, não O(n log n).
PEGA ESSA DICA!
Para decorar as complexidades médias dos principais algoritmos de ordenação, lembre-se da seguinte tabela:
Algoritmo
Caso Médio
Bubble sort
O(n²)
Insertion sort
O(n²)
Selection sort
O(n²)
Merge sort
O(n log n)
Heap sort
O(n log n)
Quick sort
O(n log n)
Counting sort
O(n + k)
Radix sort
O(d·(n+k))
Bucket sort
O(n)
A questão mescla algoritmos de complexidade linear com os de complexidade O(n log n). O merge sort é o único da lista que atende exatamente ao que foi pedido.