Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos de Ordenação — CESGRANRIO 2024

Algoritmos e Estrutura de DadosAlgoritmos de Ordenação
Código
cg021322
Banca
CESGRANRIO
Órgão
Banco da Amazônia
Ano
2024
Nível
Superior
Cargo
Técnico Científico - Tecnologia da Informação
Um analista tem disponíveis quatro algoritmos de ordenação: inserção, mergesort, heapsort e bubblesort. Como o analista não tem conhecimento sobre o tamanho do conjunto de dados e as suas condições de ordenação inicial, resolve utilizar como critério de escolha a menor complexidade do pior caso.Considerando-se esse critério de menor complexidade do pior caso, quais seriam os dois algoritmos que o analista deve utilizar para fazer uma primeira seleção?
  1. AInserção e Bubblesort
  2. BMergesort e Inserção
  3. CMergesort e Heapsort
  4. DBubblesort e Heapsort
  5. EMergesort e Bubblesort
Revelar gabarito e comentário

GabaritoC — Mergesort e Heapsort

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”.

Algoritmos de Ordenação: Complexidade de Pior Caso

Gabarito: letra C. O analista deve selecionar os algoritmos de menor complexidade no pior caso. Dentre os listados, Mergesort e Heapsort possuem complexidade O(n log n), enquanto Inserção e Bubblesort possuem O(n²). Portanto, os dois algoritmos com melhor desempenho assintótico no pior caso são Mergesort e Heapsort.

Algoritmos de ordenação
  • 1Pior caso O(n²)
    • Inserção
    • Bubblesort
  • 2Pior caso O(n log n)
    • Mergesort
    • Heapsort
LEVEL · soulevel.com.br

Análise das Alternativas

Alternativa A — ❌ Inserção e Bubblesort

Ambos têm complexidade O(n²) no pior caso, a pior entre as opções.

Alternativa B — ❌ Mergesort e Inserção

Mergesort é O(n log n), mas Inserção é O(n²). O analista buscava a menor complexidade, então Inserção não se encaixa.

Alternativa C — ✅ Correta ⟵ GABARITO

Mergesort e Heapsort são ambos O(n log n) no pior caso, representando a melhor escolha dentre os algoritmos dados.

Alternativa D — ❌ Bubblesort e Heapsort

Heapsort é O(n log n), mas Bubblesort é O(n²).

Alternativa E — ❌ Mergesort e Bubblesort

Mergesort é O(n log n), mas Bubblesort é O(n²).

PEGA ESSA DICA!

Decore as complexidades de pior caso dos principais algoritmos de ordenação:

  • Inserção: O(n²)

  • Bubblesort: O(n²)

  • Mergesort: O(n log n)

  • Heapsort: O(n log n)

  • Quicksort: O(n²) (embora o caso médio seja O(n log n))

Na dúvida, algoritmos que usam divisão e conquista ou heap tendem a ter melhor desempenho assintótico.

Gabarito: letra C

Link permanente: /questoes/cg021322