Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — IADES 2018

Algoritmos e Estrutura de DadosAlgoritmos
Código
qq357558
Banca
IADES
Órgão
CFM
Ano
2018
Nível
Superior
Cargo
Analista de Tecnologia da Informação
Quando dois elementos estão fora de ordem, há uma inversão, e esses dois elementos são trocados de posição, ficando em ordem correta. Assim, o primeiro elemento é comparado com o segundo. Se uma inversão for encontrada, a troca é feita. Em seguida, independentemente de se houve ou não troca após a primeira comparação, o segundo elemento é comparado com o terceiro, e, caso uma inversão seja encontrada, a troca é feita. O processo continua até que o penúltimo elemento seja comparado com o último. Com esse processo, garante-se que o elemento de maior valor do vetor seja levado para a última posição. A ordenação continua com o posicionamento do segundo maior elemento, do terceiro etc., até que todo o vetor esteja ordenado.CELES, W.; CERQUEIRA, R.; RANGEL, J. L. Introdução a Estruturas de Dados. Rio de Janeiro: Elsevier, 2004, com adaptações.Em relação ao algoritmo descrito, é correto afirmar que a respectiva ordem de complexidade, no pior caso, é
  1. AO(log(n))
  2. BO(n)
  3. CO(nⁿ)
  4. DO(n*log(n))
  5. EO(n²)
Revelar gabarito e comentário

GabaritoE — O(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”.

Algoritmo de Ordenação (Bubble Sort)

Gabarito: letra E. O algoritmo descrito é o Bubble Sort (ordenação por bolha), cuja complexidade no pior caso é O(n²) — quando o vetor está em ordem inversa, são realizadas aproximadamente n²/2 comparações e trocas.

A banca descreve exatamente o funcionamento do Bubble Sort: comparações sucessivas entre pares adjacentes, levando o maior elemento para o final a cada passagem, repetindo até a ordenação completa. A complexidade assintótica desse método no pior caso é quadrática.

Alternativa A — ❌ Incorreta

O(log n) é complexidade típica de busca binária, não de ordenação por comparação geral. O Bubble Sort não tem comportamento logarítmico.

Alternativa B — ❌ Incorreta

O(n) seria o caso ideal (vetor já ordenado) para Bubble Sort otimizado, mas no pior caso (ordem inversa) a complexidade é O(n²).

Alternativa C — ❌ Incorreta

O(nⁿ) é uma complexidade exponencial exagerada, não corresponde a algoritmos de ordenação clássicos.

Alternativa D — ❌ Incorreta

O(n log n) é a complexidade de algoritmos eficientes como Merge Sort, Quick Sort (caso médio) e Heap Sort, mas não do Bubble Sort.

Alternativa E — ✅ Correta ⟵ GABARITO

No pior caso, o Bubble Sort executa (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparações, que é O(n²). A cada passagem, o maior elemento "bolha" para o final, exigindo n-1 passagens no pior cenário.

NÃO CAIA NESSA!

A banca descreve o processo passo a passo, mas o candidato pode confundir com algoritmos de complexidade linear ou O(n log n). O nome "Bubble Sort" não é citado, exigindo que o aluno identifique o método pela descrição. Lembre-se: algoritmos de ordenação por comparação têm limite inferior Ω(n log n); Bubble Sort fica acima desse limite no pior caso.

Gabarito: letra E — O(n²).

Link permanente: /questoes/qq357558