Pular para o conteúdo principal

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

Algoritmos e Estrutura de DadosAlgoritmos de Ordenação
Código
cg016240
Banca
CESGRANRIO
Órgão
Banco do Brasil
Ano
2021
Nível
Médio
Cargo
Agente de Tecnologia
Dentre os problemas identificados pela gerência de um banco comercial, está a localização das contas dos seus titulares nas listagens e nos relatórios impressos em diferentes situações. Um especialista de TI sugeriu ordenar as contas por meio dos CPF dos seus n titulares antes das impressões.Dentre alguns algoritmos pré-selecionados para essa ordenação, o especialista escolheu o algoritmo de ordenação por inserção, no qual o consumo de tempo é, no melhor caso, proporcional a
  1. An log n
  2. Blog n
  3. Cn²
  4. Dn
  5. E1
Revelar gabarito e comentário

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

Algoritmos de Ordenação – Insertion Sort

Gabarito: letra D. No melhor caso, quando a lista já está ordenada, o algoritmo de ordenação por inserção (insertion sort) executa em tempo linear O(n), pois cada elemento é comparado apenas uma vez e inserido imediatamente, sem necessidade de deslocamentos.

A banca cobra a diferença entre as complexidades do insertion sort conforme o caso: melhor caso O(n), pior caso e caso médio O(n²). É essencial memorizar essas notações para algoritmos clássicos.

  1. 1Melhor caso (já ordenado)O(n)
  2. 2Caso médioO(n²)
  3. 3Pior caso (invertido)O(n²)
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

n log n é a complexidade de algoritmos como merge sort e heap sort (pior caso), não do insertion sort.

Alternativa B — ❌ Incorreta

log n é complexidade típica de busca binária, não de ordenação.

Alternativa C — ❌ Incorreta

n² é a complexidade do pior caso e do caso médio do insertion sort, mas não do melhor caso.

Alternativa D — ✅ Correta ⟵ GABARITO

No melhor caso, o insertion sort executa em O(n), pois o vetor já está ordenado e cada elemento é comparado uma única vez.

Alternativa E — ❌ Incorreta

Constante O(1) não é possível para um algoritmo que precisa percorrer todos os n elementos.

Gabarito: letra D

Link permanente: /questoes/cg016240