O cálculo de complexidade é parte essencial do projeto e da análise de algoritmos. Uma ferramenta chave usada nesta atividade é a notação Theta (Θ). Ela oferece uma maneira objetiva de descrever o comportamento assintótico de algoritmos e possibilita a comparação da eficiência entre eles.
Considerando as funções T1(n) = log2n + n e T2(n) = n, analise as asserções a seguir e a relação proposta entre elas.
I. Um algoritmo A2 com uma complexidade T2 tem uma eficiência computacional melhor que um algoritmo A1 com complexidade T1.
Porque:
II. A função T1 tem limite assintótico dado por T1(n) = Θ(T2(n)).
A seguir, assinale a alternativa correta.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
As asserções I e II são proposições falsas.
Soluções para a tarefa
Respondido por
2
Resposta:
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
Explicação:
É preciso observar que n = O(log2n + n). Adicionalmente, temos que verificar se log2n + n = O(n), ou seja, log2n + n ≤ cn, c > 0. Como log2n ≤ n (pois n ≤ 2n), temos que log2n + n ≤ 2n, tomando c = 2 e n ≥ 1. Portanto, T1(n) = Θ(T2(n)).
Perguntas interessantes