Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Limite superior assintótico de \( x \cdot \log(x) \)

0 votos
28 visitas
perguntada Out 2 em Ciência da Computação por Matheus Cintrão (16 pontos)  

O problema é apresentado no exercício 3.3 do capítulo 3 do livro ”Introduction to Recursive Programming“.

No exercício pede-se a demostração de que \[ x \cdot \log(x) \in O(n^{1+a}) , a > 0\] usando limite e regra de L'Hopital

Ou seja, que \(n^{1+a}\) é um limite superior de \( x \cdot \log(x) \) para \( a > 0\)

Compartilhe

1 Resposta

0 votos
respondida Out 2 por Matheus Cintrão (16 pontos)  
editado Out 2 por Matheus Cintrão

Ao estudarmos eficiência de algorítimos utilizamos os conceito de limites assintóticos para determinar a ordem grandeza do crescimento da demando computacional de um determinado algorítimo em relação a uma variável unidimensional \(n\) relacionada ao tamanho do problema (numero de dados, por exemplo). Temos 3 tipos de limites assintóticos: Superior( \(O(g(n))\)), Inferior( \((\Omega(n))\)) e "Justo"( \((\Theta(g(n))\)).

Para saber se uma função \(f(n) \in O(g(n)) \) precisamos que:
\[ lim_{n \to \infty}{\frac{f(n)}{g(n)}}< \infty \]

Ou seja, precisamos que este limite seja uma constante ou zero.

Basta, portanto, demostrarmos que
\[ lim_{n \to \infty}{\frac{x \cdot \log{n}}{n^{1+a}}} = 0 \]

Temos que

\[ lim_{n \to \infty}{\frac{x \cdot \log{n}}{n^{1+a}}} = \frac{\infty}{\infty} , a>0 \]

Podemos portanto aplicar L'Hopital:

\[ lim_{n \to \infty}{\frac{\log{n} + 1} {(1+a) \cdot n^{a}}} = \frac{\infty}{\infty} , a>0\]

Aplicando L'Hopital novamente:

\[ lim_{n \to \infty}{\frac{\frac{1}{n}} {(1+a)\cdot a \cdot n^{a-1}}} = lim_{n \to \infty}{\frac{1}{(1+a)\cdot a \cdot n^{a}}}= \frac{1}{\infty} = 0 <\infty \]</p>

Temos portanto que \( n\cdot\log{n} \in O(n^{1+a}), a>0 \)

Para exemplificar podem plotar as funções em gráfico, o código é bastante simples:

import matplotlib.pyplot as plt
import numpy as np

x = np.arange(1, 1000002, 10)
fig, ax = plt.subplots()  
ax.plot(x, x*np.log(x), label='nlog(n)')
ax.plot(x, x**1.2, label='a=0.2')  
ax.plot(x, x**1.25, label='a=0.2')  
ax.plot(x, x**1.3, label='a=0.3') 
ax.set_xlabel('n')
ax.set_ylabel('y') 
ax.set_title('Plotando funções')  
ax.legend()  

Segue um gráfico das funções para os seguintes valores de a: 0.20, 0.25, 0.30.

A imagem será apresentada aqui.

Para valores pequenos de a a função \(n\log{n}\) tem valores maiores durante um longo intervalo de valores, mas, como demostrado matematicamente, a função \( n^{1+a}\) eventualmente a ultrapassará.

comentou Out 7 por Thiago Trafane (21 pontos)  
Matheus, em primeiro lugar, parabéns pela solução! Quanto aos meus comentários:

1) Você assumiu que \( \log (n) \) se refere ao logaritmo natural de \(n\). Olhando o livro, não tive essa certeza. Por via das dúvidas, talvez fosse interessante fazer a prova considerando o logaritmo numa base \(b \) qualquer. A demonstração é bastante semelhante à que você fez.

2) No enunciado da questão e nas primeiras manipulações do limite, você usou \( x \) e \(n\) nas mesmas expressões, o que não está correto. Seria bom corrigir isso. Assim, no enunciado, teríamos, por exemplo, \(n \cdot \log (n) \in O(n^{1+a})\) e não \(x \cdot \log (x) \in O(n^{1+a})\).

3) No seu programa, o label do gráfico com \( a = 0.25 \) está errado.

4) No primeiro parágrafo acredito que haja um erro de digitação: onde você escreveu "demando computacional" seria "demanda computacional".
...