Questão de Algoritmos e Estrutura de Dados — Algoritmos — COPESE - UFPI 2017
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq249358
Banca
COPESE - UFPI
Órgão
UFPI
Ano
2017
Nível
Superior
Cargo
COPESE - - Analista de Tecnologia da Informação
A ideia da ordenação por bolha (Bubble Sort) é percorrer o vetor de elementos sequencialmente e, em cada passagem comparar cada elemento com seu sucessor, fazendo-o chegar ao topo da sequência. Dado que n é o número de elementos do vetor, a complexidade do pior caso desse algoritmo é
AO(n).
BO(n² ).
CO(n+1).
DO(n log n).
EO(log n).
Revelar gabarito e comentário▾
GabaritoB — 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”.
Bubble Sort e Complexidade de Algoritmos
Gabarito: letra B. A complexidade de tempo do algoritmo Bubble Sort no pior caso é O(n²), pois para cada elemento (n) ele realiza uma varredura completa comparando com os demais (também n), resultando em aproximadamente n²/2 comparações.
A banca cobra o conhecimento da notação Big O para algoritmos clássicos de ordenação. No Bubble Sort, o pior caso ocorre quando o vetor está na ordem inversa, e o algoritmo precisa executar n-1 passagens, cada uma comparando e trocando elementos adjacentes, totalizando O(n²) operações.
1Vetor na ordem inversa
2n-1 passagens
3Cada passagem: n-1 comparações
4Total: ~n²/2 operações
5Complexidade: O(n²)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
Afirma O(n). Essa complexidade é típica de algoritmos lineares, como percorrer um vetor uma única vez. O Bubble Sort, mesmo no melhor caso (vetor já ordenado com otimização), ainda pode ser O(n) com a flag de troca, mas no pior caso é O(n²).
Alternativa B — ✅ Correta ⟵ GABARITO
O Bubble Sort possui complexidade O(n²) no pior caso (vetor invertido) e também no caso médio. A cada passagem, o maior elemento "flutua" para o final, e são necessárias n-1 passagens, cada uma com até n-1 comparações, resultando em O(n²).
Alternativa C — ❌ Incorreta
O(n+1) é uma notação equivalente a O(n), pois constantes e termos de menor ordem são ignorados. Portanto, não corresponde à complexidade quadrática do Bubble Sort.
Alternativa D — ❌ Incorreta
O(n log n) é a complexidade de algoritmos eficientes como Merge Sort, Quick Sort (caso médio) e Heap Sort. O Bubble Sort é mais lento, sendo O(n²).
Alternativa E — ❌ Incorreta
O(log n) é a complexidade de algoritmos como busca binária em um vetor ordenado. O Bubble Sort realiza ordenação, não busca, e exige muito mais operações.
PEGA ESSA DICA!
Para fixar, lembre-se que o Bubble Sort é um dos algoritmos mais lentos (O(n²)) entre os de ordenação por comparação. Os principais algoritmos e suas complexidades no pior caso são: Bubble Sort O(n²), Selection Sort O(n²), Insertion Sort O(n²), Merge Sort O(n log n), Heap Sort O(n log n), Quick Sort O(n²) no pior caso (mas O(n log n) no médio).