Repita o exercício 23, para as funções:

n_{√n log_2 n}; (log_2 n)^2

Passo 1

Galera, queremos saber quais dos algoritmos é mais eficiente. Portanto, estamos diante de uma questão sobre taxas relativas de crescimento. Vamos calcular os limites??

underset(n -> oo)(lim) (( log_2 n )^2)/(n) = underset(n -> oo)(l i m) (((ln n)/(ln 2))^2)/(n) = underset(n -> oo)(l i m) (( ln n )^2)/(n ( ln 2 )^2)

= n underset(n -> oo)(l i m) (2 ( ln n ) (1)/(n))/(( ln 2 )^2) = (2)/(( ln 2 )^2) underset(n -> oo)(l i m) (ln n)/(n)

= (2)/(( ln 2 )^2) underset(n -> oo)(l i m) ((1)/(n))/(1) = 0

Assim, ( log_2 n )^2 cresce mais lentamente que n . Agora, vamos verificar para a função que ainda falta.

underset(n -> oo)(l i m) (( log_2 n )^2)/(sqrt(n) log_2 n) = underset(n -> oo)(l i m) (log_2 n)/(sqrt(n)) = underset(n -> oo)(l i m) (((ln n)/(ln 2)))/(n^((1)/(2))) = (1)/(ln 2) underset(n -> oo)(l i m) (ln n)/(n^((1)/(2)))

= (1)/(ln 2) underset(n -> oo)(l i m) ((1)/(n))/((1)/(2) n^(- (1)/(2))) = (2)/(ln 2) underset(n -> oo)(l i m) (1)/(n^((1)/(2))) = 0

( log_2 n )^2 cresce mais lentamente que sqrt(n) log_2 n

Assim, concluímos que o algoritmo mais eficiente é y = n

Passo 2

A imagem gráfica será:

Resposta

  1. o algoritmo mais eficiente é y = n
  2. Gráfico
Ver Outros Exercícios desse livro

Exercícios de Livros Relacionados