Quando dois elementos estão fora de ordem, há uma inversã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, é
Gabarito comentado
Confira o gabarito comentado por um dos nossos professores
A alternativa correta é a E - O(n²).
Vamos entender por que essa é a alternativa correta e analisar as alternativas incorretas.
O enunciado descreve um algoritmo de ordenação muito conhecido: o Bubble Sort. No Bubble Sort, cada elemento de uma lista é comparado com o próximo elemento e trocado se estiver fora de ordem. Esse processo é repetido, garantindo que, ao final de cada iteração, o maior elemento "bolha" para a última posição, e assim sucessivamente até que a lista esteja completamente ordenada.
Para determinar a complexidade de tempo desse algoritmo, especialmente no pior caso, precisamos analisar quantas vezes as comparações e trocas são feitas:
- Suponha uma lista com n elementos. Na primeira iteração, o algoritmo faz n-1 comparações.
- Na segunda iteração, faz-se n-2 comparações, e assim por diante, até que na última iteração, há apenas uma comparação.
Isso resulta no somatório dos primeiros n números naturais: 1 + 2 + 3 + ... + (n-1), o que é equivalente a O(n²).
Agora, vamos justificar as alternativas incorretas:
A - O(log(n)): Essa complexidade está associada a algoritmos que dividem o problema em subproblemas menores de tamanho proporcional (como a busca binária). O Bubble Sort não se encaixa nesse padrão.
B - O(n): Algoritmos com essa complexidade realizam um número linear de operações, como percorrer uma lista uma vez. O Bubble Sort faz muito mais que isso, especialmente no pior caso.
C - O(nⁿ): Essa complexidade é extremamente alta e se aplica a algoritmos exponenciais ou super-exponenciais (o que não é o caso aqui). O Bubble Sort, apesar de ser ineficiente, não chega a tanto.
D - O(n*log(n)): Essa é a complexidade de algoritmos de ordenação mais eficientes, como o Merge Sort e o Quick Sort no caso médio. O Bubble Sort é menos eficiente.
Portanto, a alternativa E - O(n²) é a correta, pois reflete a complexidade do algoritmo Bubble Sort no pior caso.
Espero que essa explicação tenha sido clara e que você tenha compreendido por que a alternativa E é a correta. Se tiver mais dúvidas, estarei à disposição para ajudar!
Clique para visualizar este gabarito
Visualize o gabarito desta questão clicando no botão abaixo
Comentários
Veja os comentários dos nossos alunos
A questão trata-se do método Bolha “bubble sort”
E ordem de complexidade, no pior caso, é O(n²)
Fonte: Citada no enunciado da questão
Complementando à nivel de curiosidade:
Melhor caso: O(n)
Médio caso:O(n²)
Pior caso:O(n²)
Porque não O(n^n)? Se analisarmos matematicamente apresenta um grau de complexidade maior.
Força Guerreiro!!!!!!
Clique para visualizar este comentário
Visualize os comentários desta questão clicando no botão abaixo
Conheça nossos planos