Questão 3527974

• Banca: INSTITUTO AOCP
• Órgão: UFFS
• Ano: 2016
• Provas: INSTITUTO AOCP - 2016 - UFFS - Técnico de Tecnologia da Informação
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Na análise de complexidade de algoritmos, em que o interesse é restrito a valores assintóticos e se desconsidera as constantes multiplicativas e aditivas, qual é o número de passos a ser considerado na expressão 2(n²-1) + 10n³?

• A. 2(n²-1)
• B. 10
• C. 2n
• D. n³
• E. n²-1

Gabarito: D

Comentários

• Quando se considera o número de passos efetuados por um algoritmo podem-se desprezar constantes aditivas ou multiplicativas. Por exemplo, um valor de número de passos igual a 3n será aproximado para n. Além disso, como o interesse é restrito a valores assintóticos, termos de menor grau também podem ser desprezados. Assim, um valor de número de passos igual a n² + n será aproximado para n². O valor 6n³ + 4n – 9 será transformado em n³.

  Alternativa: D

• Força Guerreiro!!!!!!