Questão 2639767

• Banca: IADES
• Órgão: CFM
• Ano: 2018
• Provas: IADES - 2018 - CFM - Analista de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

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, é

• A. O(log(n))
• B. O(n)
• C. O(nⁿ)
• D. O(n*log(n))
• E. O(n²)

Gabarito: E

Comentários

• 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!!!!!!