Questão 2324854

• Banca: IFB
• Órgão: IFB
• Ano: 2017
• Provas: IFB - 2017 - IFB - Professor - Informática
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

Leia as afirmativas a seguir considerando que f(n) e g(n) são funções positivas.

I) Se g(n) é O(f(n)), um algoritmo de função de complexidade de tempo f(n) possui Ordem de complexidade g(n).

II) Se g(n) é O(f(n)), f(n) é um limite superior para g(n).

III) Se a função g(n) = 7.log(n) +6 , então a função g(n) é O(log(n)).

IV) Se g(n) = n² e f(n) = (n+1)² temos que g(n) é O(f(n)) e f(n) é O(g(n)).

V) Se g(n) = 2ⁿ⁺¹ e f(n) = 2ⁿ temos que g(n) = O(f(n)).

Assinale a alternativa que apresenta somente as afirmativas CORRETAS.

• A. I, II, IV, V.
• B. II, III, IV.
• C. II, III, IV, V.
• D. I, III, IV, V.
• E. II, III, V.

Gabarito: C

Comentários

• Definição: Dadas funções assintoticamente não negativas f e g, dizemos que f está na ordem Ο de g  e escrevemos  f = Ο(g)   se   f(n)  ≤  c · g(n)   para algum c positivo e para todo n suficientemente grande.  Em outras palavras, existe um número positivo c e um número n0 tais que f(n) ≤ c · g(n) para todo n maior que n0.

  I) Se g(n) é O(f(n)), um algoritmo de função de complexidade de tempo g(n) possui Ordem de complexidade f(n). ERRADO

  II) Se g(n) é O(f(n)), f(n) é um limite superior para g(n). CORRETO

  III) Se a função g(n) = 7.log(n) +6 , então a função g(n) é O(log(n)). CORRETO: g(n) ≤ 13 · log(n)

  IV) Se g(n) = nˆ2 e f(n) = (n+1)ˆ2 temos que g(n) é O(f(n)) e f(n) é O(g(n)). CORRETO, mesma complexidade

  V) Se g(n) = 2ˆ(n+1) e f(n) = 2ˆn temos que g(n) = O(f(n)). CORRETO g(n) ≤ 2 · f(n)

• Força Guerreiro!!!!!!