Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESPE / CEBRASPE 2022

Algoritmos e Estrutura de DadosAlgoritmos
Código
ce133705
Banca
CESPE / CEBRASPE
Órgão
BNB
Ano
2022
Nível
Superior
Cargo
Analista de Sistemas - Desenvolvimento de Sistemas
No que se refere aos conceitos de ordenamento, julgue o seguinte item.A complexidade de tempo do algoritmo bubble sort é do tipo O(n × logn), logo, no caso desse algoritmo, o tempo de execução aumenta exponencialmente com o acréscimo do valor de n.
  1. CCerto
  2. EErrado
Revelar gabarito e comentário

GabaritoE — Errado

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

Bubble Sort: Complexidade de Tempo

❌ ERRADO. A afirmação contém dois erros: (1) a complexidade do bubble sort é O(n²), e não O(n log n); (2) O(n log n) não representa crescimento exponencial, mas log-linear. O tempo de execução do bubble sort cresce quadraticamente com n.

O algoritmo bubble sort, no pior caso (lista invertida), realiza aproximadamente n²/2 comparações e trocas, resultando em complexidade O(n²). A notação O(n log n) é típica de algoritmos eficientes como merge sort ou heapsort. Já o crescimento exponencial (como O(2ⁿ)) é muito mais acelerado e não se aplica aqui.

Afirmação

Complexidade real do Bubble Sort

Complexidade citada

Tipo de crescimento do O(n log n)

Conclusão

Complexidade do Bubble Sort

O(n²)

O(n log n)

Log-linear (não exponencial)

Errado

Crescimento do tempo

Quadrático (n²)

Exponencial (2ⁿ)

Não se aplica

Errado

❌ ERRADO.

Link permanente: /questoes/ce133705