Qual é a complexidade temporal do algoritmo Bubble Sort no pior caso?
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Qual é a complexidade temporal do algoritmo Bubble Sort no pior caso?
- A) O(n)
- B) O(n log n)
- C) O(n²)
- D) O(log n)
- E) O(1)
✅ Resposta correta: alternativa C
Resolução passo a passo
- O Bubble Sort percorre a lista repetidamente, comparando pares vizinhos e trocando-os quando estão fora de ordem. Cada passagem completa leva até n-1 comparações, e são necessárias até n-1 passagens para que a lista fique ordenada.
- No pior caso, a lista está em ordem inversa e todas as comparações resultam em troca. O número total de comparações é (n-1) + (n-2) + ... + 1, que soma n(n-1)/2.
- Desprezando termos de menor grau e constantes, n(n-1)/2 cresce na ordem de n^2. Logo, a complexidade de pior caso é O(n^2), alternativa C, que coincide com o gabarito oficial.
- A alternativa A (O(n)) está errada porque o algoritmo não percorre a lista apenas uma vez; ele precisa de várias passagens. A alternativa B (O(n log n)) está errada porque é a complexidade típica de algoritmos eficientes como Merge Sort e Quick Sort na média. A alternativa D (O(log n)) está errada porque o número de operações cresce mais rápido que o logaritmo do tamanho da entrada. A alternativa E (O(1)) está errada porque o tempo de execução depende do tamanho da lista e não é constante.
💡 Dica: Lembre-se da definição de complexidade de algoritmos.
Alternativa por alternativa
Acredita que, como o algoritmo percorre a lista, basta uma passagem linear para ordená-la. Ignora que trocas de vizinhos podem exigir várias passagens completas.
Confunde o Bubble Sort com algoritmos de divisão e conquista como Merge Sort e Quick Sort, associando a ordenação ao custo n log n.
Por que engana: Confundir a complexidade do pior caso com a do melhor caso, subestimando o tempo de execução do Bubble Sort.
Bubble Sort tem complexidade O(n²) no pior caso.
Associa a ordenação a buscas com divisão do espaço de busca, como a busca binária, e aplica o logaritmo a um algoritmo que não divide a entrada.
Imagina que a ordenação pode ser feita com um número fixo de operações, como se o algoritmo acessasse a resposta diretamente sem examinar os elementos.
Raio-X da questão
complexidade temporal
avaliacao
complexidade temporal · algoritmos de ordenacao
Revisar a análise de complexidade de algoritmos, especialmente o Bubble Sort.
Confundir a complexidade do pior caso com a do melhor caso, subestimando o tempo de execução do Bubble Sort.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para um algoritmo que percorre um vetor dados de tamanho N verificando cada elemento até achar um alvo, qual a…
- Descreva como um algoritmo de ordenação funciona, utilizando o método Bubble Sort como exemplo. Esclareça suas etapas…
- Dado um vetor (array) não ordenado com n elementos, qual é a complexidade temporal, no pior caso, do algoritmo que…
- Num algoritmo de ordenação que usa dois índices em laços aninhados para percorrer um vetor de N nomes, como a variável N…
- Compare os algoritmos de ordenação bubble sort e quicksort, identificando suas características.
- Considere um algoritmo que para cada um dos N elementos de um vetor executa, no pior caso, uma busca linear sobre M…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog