Questão 137215

• Banca: CESGRANRIO
• Órgão: Casa da Moeda
• Ano: 2009
• Provas: CESGRANRIO - 2009 - Casa da Moeda - Analista de Nível Superior - Desenvolvimento de Sistemas
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

No desenvolvimento de um sistema de análise financeira, um programador utilizou um algoritmo cuja complexidade de tempo, no pior caso, é igual a O(n).
Outro programador aponta um algoritmo de melhor complexidade igual a

• A. O(log n).
• B. O(n log n).
• C. .
• D. .
• E. O(n!).

Gabarito: A

Comentários

• Volto a dizer:
  
  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!)

•  

  O examinador passou o valor (n) e quer um algoritmo de melhor complexidade, ou seja, quer um algoritmo mais eficiente que (n).

   

  (A) O(log n).(ao analisar a tabela abaixo constata-se que (logn) é o MENOS complexo e mais eficiente entre os citados.)
  (B) O(n log n).
  (C) O(n2)
  (D) O(2n)
  (E) O(n!)

   

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

  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

   

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

  OBS2. A eficiência vai diminuindo, ou seja, CONSTANTE 1 é a mais eficiente, já a exponencial é a menos eficiente.

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