Questão 5279629

• Banca: Marinha
• Órgão: Comando do 2º Distrito Naval
• Ano: 2020
• Provas: Marinha - 2020 - Comando do 2º Distrito Naval - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Coloque F (falso) ou V (verdadeiro) nas funções abaixo, considerando a notação de complexidade O, e assinale a seguir a opção correta.

( ) f - 9 + log n = 0(n)

( ) f= 255 = 0(1)

( ) f = 37 + 2¹⁵ⁿ = 0(2ⁿ)

( ) f=25 + 2¹⁸⁺ⁿ = 0(2ⁿ)

• A. (V) (V) (V) (F)
• B. (V) (V) (F) (V)
• C. (F) (F) (V) (V)
• D. (F) (V) (V) (F)
• E. (V) (F) (V) (F)

Gabarito: B

Comentários

• Quando se fala de complexidade utilizando o BIG O, pode-se desprezar constantes aditivos e multiplicativas.

  Nesse caso a questão está querendo saber qual é a complexidade de pior caso. Para saber isso é necessário saber quais são as possíveis complexidades e sua ordem.

  O(1) = Constante

  O(log n) = logarítmica

  O(log^2 n) = log quadrática

  O(n log n) = n log n

  O(n) = linear

  O(n^2) = quadrática

  O(n^3) = cubica

  O(2^n) = exponencial

  ================================

  f - 9 + log n = 0(n) => CERTO

  f= 255 = 0(1) => CERTO

  f = 37 + 215n = 0(2n) => ERRADO - O(2^15N) possui a maior complexidade que a O(2^n)

  f=25 + 218+n = 0(2n) => CERTO

  Alternativa: B