Questão de Algoritmos e Estrutura de Dados — Algoritmos — FUNDATEC 2026
Algoritmos e Estrutura de Dados›Algoritmos
Código
qg685875
Banca
FUNDATEC
Órgão
IFC-SC
Ano
2026
Nível
Superior
Cargo
Professor EBTT - Informática
Considerando a notação Big-O e o comportamento dos principais algoritmos de busca e ordenação, assinale a alternativa que apresenta, correta e respectivamente, a descrição da complexidade e das características do algoritmo Merge Sort.
APossui complexidade O(n²) no pior caso e opera sem necessidade de memória auxiliar adicional.
BPossui complexidade O(n log n) no pior caso e não requer memória auxiliar por operar diretamente sobre o vetor original.
CPossui complexidade O(log n) no pior caso por dividir o conjunto de dados recursivamente ao meio a cada iteração.
DPossui complexidade O(n log n) apenas no melhor caso, degradando para O(n²) no caso médio quando o conjunto de dados está parcialmente ordenado.
EPossui complexidade O(n log n) no pior caso, utiliza divisão e conquista e requer memória auxiliar proporcional ao tamanho da entrada.
Revelar gabarito e comentário▾
GabaritoE — Possui complexidade O(n log n) no pior caso, utiliza divisão e conquista e requer memória auxiliar proporcional ao tamanho da entrada.
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”.
Merge Sort e notação Big-O
Gabarito: letra E. O Merge Sort possui complexidade O(n log n) no pior caso (e nos demais), utiliza o paradigma de divisão e conquista e requer memória auxiliar proporcional ao tamanho da entrada (O(n)). Esse é um conceito fundamental sobre o algoritmo, e a alternativa E descreve corretamente todas essas características.
A questão cobra a correta associação entre a complexidade assintótica (Big-O) e as propriedades do Merge Sort. É importante lembrar que, diferentemente de algoritmos como Quick Sort (que tem pior caso O(n²)), o Merge Sort mantém a complexidade O(n log n) em todas as situações. Além disso, ele não é um algoritmo in-place, pois necessita de vetor auxiliar para realizar a intercalação das partições.
Merge Sort: Complexidade (O(n log n) em todos os casos, Melhor, médio e pior); Paradigma (Divisão e conquista); Memória (Requer auxiliar O(n), Não é in-place); Estabilidade (Desempenho estável, Independente da ordenação prévia)
Alternativa A — ❌ Incorreta
Afirma que o Merge Sort possui complexidade O(n²) no pior caso e opera sem necessidade de memória auxiliar. Ambas as afirmações são falsas: a complexidade do Merge Sort é O(n log n) em todos os casos, e ele exige memória auxiliar O(n) para a intercalação. O valor O(n²) corresponde, por exemplo, aos algoritmos Bubble Sort, Selection Sort e Insertion Sort (no pior caso).
Alternativa B — ❌ Incorreta
Acerta a complexidade (O(n log n) no pior caso), mas erra ao afirmar que não requer memória auxiliar. O Merge Sort não é in-place: necessita de espaço extra proporcional ao tamanho do vetor para realizar as operações de merge. Portanto, a segunda parte invalida a alternativa.
Alternativa C — ❌ Incorreta
Afirma que a complexidade é O(log n). O(log n) é a ordem de grandeza de algoritmos como a busca binária, que dividem o problema pela metade sem percorrer todos os elementos. O Merge Sort, apesar de também dividir recursivamente, precisa recombinar os elementos, resultando em O(n log n).
Alternativa D — ❌ Incorreta
Afirma que o Merge Sort tem complexidade O(n log n) apenas no melhor caso e que degrada para O(n²) no caso médio quando o conjunto está parcialmente ordenado. Isso não é verdade: o Merge Sort apresenta complexidade O(n log n) em todos os casos (melhor, médio e pior), independentemente da ordenação prévia dos dados. Essa estabilidade de desempenho é uma de suas principais características.
Alternativa E — ✅ Correta ⟵ GABARITO
Descreve corretamente o Merge Sort: complexidade O(n log n) no pior caso, uso da estratégia de divisão e conquista e necessidade de memória auxiliar proporcional ao tamanho da entrada (O(n)). Todos os elementos estão de acordo com a definição clássica do algoritmo.