Questão 142219

• Banca: CESGRANRIO
• Órgão: BNDES
• Ano: 2009
• Provas: CESGRANRIO - 2009 - BNDES - Profissional Básico - Análise de Sistemas - Desenvolvimento
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Seja n o tamanho da entrada de um algoritmo para um problema P. Cada alternativa, que corresponde a um algoritmo distinto, apresenta o número de operações necessárias para resolver P. Considerando-se a análise assintótica (Big O notation), qual algoritmo possui menor complexidade?

• A. 2 + 10log n
• B.
• C.
• D. 5n + 128
• E.

Gabarito: A

Comentários

• A ordem de cima ai esta errada. O correto é:
  
  O(1) -> O(logn) -> O (n) -> O (nlog n) -> O(n^2) -> O (n^3) -> O (2^n ) -> O (n!)
• Lembrando que:
  • O(2 + 10log n) = O(log n)
  • O(3n²+n) = O(n²)
  • O(1000+2n³) = O(n³)
  • O(5n+128) = O(n)
  • O(4ⁿ)
  Em ordem crescente de complexidade temos:
  •   O(log n) < O(n) < O(n²) < O(n³) < O(4ⁿ)
• Ilustrando os comentários acima:
  
• Cabe colocar também algumas das principais estruturas de dados/algoritmos de busca quanto à sua complexidade:

• Simplificando :
  

  (A) 2 + 10log n - Complexidade logarítmica

  (B) 3n² + n - Complexidade quadrática

  (C) 1000 + 2n^{3 -} Complexidade cúbica
  
  (D) 5n + 128 - Complexidade linear
  
  (E) 4^{n    -} Complexidade exponencial
  
  A resposta correta é letra (A), pois dentre as complexidades das alternativas da questão a logarítmica é a menor.
  Como informa a tabela do colega acima postada.

  
  

• 1 PASSO: eliminar os números (eliminação em vermelho):

  (A) 2 + 10logn
  (B) 3n2 + n
  (C) 1000 + 2n3
  (D) 5n + 128
  (E) 4n

   

  2 PASSO: eliminar as funções menos complexas em detrimento as mais complexas (eliminação em negrito):

  (A) 2 + 10logn
  (B) 3n2 + n (OBSERVE AQUI QUE O MAIS COMPLEXO SEMPRE ELIMINARÁ O MENOS COMPLEXO, PORTANTO O n ta FORA)
  (C) 1000 + 2n3
  (D) 5n + 128
  (E) 4n

   

  3 PASSO: Analisar os resultados e assinalar qual é o mais complexo:

  (A) 2 + 10logn ----> logn (ESSE É O RESULTADO COM A FUNÇÃO MENOS COMPLEXA, PORTANTO É O GABARITO)
  (B) 3n2 + n ---> n2
  (C) 1000 + 2n3 ---> n3
  (D) 5n + 128 ---> n
  (E) 4n ---> 4n

   

  --------------------------------------------------------------------------------------------------------------------------------------

  A tabela que tem que ter tatuada no cerebro:

   

  CONSTANTE  | LOGARITMO | LINEAR  | NLOGN  | quadrática    |cúbica | EXPONENCIAL
  1                      | logn                | n             | nlogn     | n2                  |n3        | an

   

  OBS. A complexidade vai aumentando, ou seja, CONSTANTE 1 é a menos complexa, já a exponencial é a mais complexa

  --------------------------------------------------------------------------------------------------------------------------------------