Questão de Algoritmos e Estrutura de Dados — Algoritmos — IV - UFG 2024
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg267028
Banca
IV - UFG
Órgão
IF-SE
Ano
2024
Nível
Superior
Cargo
Professor EBTT - Informática
O estudo da complexidade de algoritmos é essencial para garantir que uma mesma tarefa possa ser realizada de modo mais eficiente do que utilizando soluções que demandem maior custo de processamento. A complexidade de tempo do algoritmo Merge Sort, quando ordenando uma lista de tamanho n, é:
AO(n)
BO(n²)
CO(n log n)
DO(2n)
Revelar gabarito e comentário▾
GabaritoC — O(n log 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 Merge Sort
Gabarito: letra C. O Merge Sort possui complexidade de tempo O(n log n) no pior, médio e melhor caso, característica dos algoritmos de ordenação baseados em comparação que utilizam a estratégia de divisão e conquista.
A questão cobra o conhecimento clássico de complexidade de algoritmos de ordenação. O Merge Sort divide a lista ao meio recursivamente e depois intercala as partes, resultando em log n níveis de recursão, cada um processando n elementos.
1Divide lista ao meio
2Recursão em log n níveis
3Intercala partes (n por nível)
4Resultado: O(n log n)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O(n) é a complexidade de algoritmos lineares, como busca linear, e não se aplica ao Merge Sort.
Alternativa B — ❌ Incorreta
O(n²) é a complexidade de algoritmos como Bubble Sort, Insertion Sort e Selection Sort no pior caso. Merge Sort é mais eficiente.
Alternativa C — ✅ Correta ⟵ GABARITO
O(n log n) é a complexidade correta. O Merge Sort garante esse desempenho mesmo no pior caso.
Alternativa D — ❌ Incorreta
O(2n) é uma notação incomum e, na prática, reduz-se a O(n), que não corresponde ao Merge Sort.