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 te...
Complexidade de Algoritmos
Estefania Porto

Question

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...

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)=n2 e f(n)=(n+1)2 temos que g(n) é O(f(n)) e f(n) é O(g(n)). V- Se g(n) = 2n+1 e f(n) = 2n temos que g(n) = O(f(n)).

Algoritmos

•

ESTÁCIO

1

0

1

0

2

Fabiane Navarro

31/05/2023

Ed · Answer

A alternativa correta é:

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

Explicação:
I- Se g(n) é O(f(n)), isso significa que g(n) cresce no máximo tão rápido quanto f(n). Portanto, 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). Essa afirmativa está incorreta, pois f(n) é um limite superior para g(n) apenas se g(n) é Ô(f(n)).

III- Se a função g(n) = 7.log(n) +6 , então a função g(n) é O(log(n)). Essa afirmativa está correta, pois a função g(n) cresce no máximo tão rápido quanto log(n).

IV- Se g(n)=n2 e f(n)=(n+1)2 temos que g(n) é O(f(n)) e f(n) é O(g(n)). Essa afirmativa está incorreta, pois g(n) não é O(f(n)) e f(n) não é O(g(n)). Na verdade, g(n) é Ô(f(n)) e f(n) é Ô(g(n)).

V- Se g(n) = 2n+1 e f(n) = 2n temos que g(n) = O(f(n)). Essa afirmativa está correta, pois g(n) cresce no máximo tão rápido quanto f(n).

herik.dev92 · Answer

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

Essa afirmativa está incorreta. Quando dizemos que g(n) é O(f(n)), significa que g(n) está limitado superiormente por f(n), e não o contrário. Portanto, não podemos afirmar que um algoritmo com complexidade f(n) terá obrigatoriamente uma complexidade g(n).

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

Essa afirmativa está correta. Quando dizemos que g(n) é O(f(n)), isso implica que g(n) está limitado superiormente por f(n). Portanto, 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)).

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...

Algoritmos

ESTÁCIO

💡 2 Respostas

Faça como milhares de estudantes: teste grátis o Passei Direto

Agora você pode testar o

Passei Direto grátis

✏️ Responder

Outros materiais

Perguntas relacionadas

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...

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 te...

Leia as afirmações 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 tem...

Leia as af irmativas 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...

Materiais relacionados

Outros materiais