1. Suponha que você tenha três algoritmos diferentes para resolver o mesmo problema e que cada um deles dependa de uma série de passos que é da ordem de uma das funções listadas aqui:
  2. n log 2 ⁡ n ; n 3 2 ; n   ( log 2 ⁡ n ) 2

    Qual dos algoritmos é mais eficiente a longo prazo?

  3. Trace em um mesmo gráfico as funções do item a para obter uma noção da velocidade com que cada uma cresce.

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

lim n → ∞ ⁡ n   log 2 ⁡ n n log 2 ⁡ n 2 =   l i m n → ∞   1 log 2 ⁡ n = 0  

Assim, n   log 2 ⁡ n cresce mais lentamente que n log 2 ⁡ n 2 . Agora, vamos verificar para a função que ainda falta.

lim ⁡                   n   log 2 ⁡ n n 3 2 = l i m n → ∞   ln ⁡ n   ln ⁡ 2   n 1 2   n → ∞

=   1 ln ⁡ 2   l i m n → ∞ 1 n 1 2 n - 1 2 = 2 ln ⁡ 2   l i m n → ∞   1 n 1 2 = 0  

n   log 2 ⁡ n cresce mais lentamente que n 3 2 .

Assim, concluímos que o algoritmo mais eficiente é n log 2 ⁡ n 2

Passo 2

A imagem gráfica será:

Resposta

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

Exercícios de Livros Relacionados