FC ConcursosFC Concursos

Questão FC374700

Algoritmos de ordenação são responsáveis por ordenar elementos de uma estrutura de dados de forma completa ou parcial. Sobre a complexidade dos algoritmos de ordenação, assinale, a

Algoritmos e Lógica de Programação

Instituto Consulplan · 2023

Algoritmos de ordenação são responsáveis por ordenar elementos de uma estrutura de dados de forma completa ou parcial. Sobre a complexidade dos algoritmos de ordenação, assinale, a seguir, o algoritmo de ordenação que, no pior caso, tem complexidade igual a O(n log n).

  1. Quick sort.
  2. Merge sort.
  3. Bubble sort.
  4. Insertion sort.
  5. Selection sort.
Mostrar resposta e comentário

Gabarito

B

Comentário do professor

Merge Sort é um algoritmo baseado em divide e conquista: a entrada é dividida recursivamente em duas metades, cada metade é ordenada e os resultados são intercalados (merge).

A análise de custo segue a recorrência \(T(n)=2T(n/2)+\Theta(n)\), onde \(\Theta(n)\) corresponde ao trabalho de intercalar duas metades.

Pela aplicação do Teorema Mestre, essa recorrência resolve para \(T(n)=\Theta(n\log n)\), portanto a complexidade no pior caso é \(O(n\log n)\).

Além disso, Merge Sort é estável e preserva a ordem relativa de elementos iguais, mas requer memória adicional de \(O(n)\) para as operações de merge.

Conteúdo do catálogo FC Concursos · Atualizado em

Continue aprendendo