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

Eficiência de Algoritmos

0 votos
8 visitas
perguntada Ago 29 em Economia por CICERO FILHO (26 pontos)  
editado Ago 29 por CICERO FILHO

Utilizando limites, mostre que \(log\ n!\) \( \in\) \( \Theta\) \(( n\log_{}n\))

Referência: Exercício 3.2 - Cap 3 – Runtime Analysis of Recursive Algorithms – do livro “Introduction to Recursive Programming” - Manuel Rubio-Sánchez.

Compartilhe

1 Resposta

0 votos
respondida Ago 29 por CICERO FILHO (26 pontos)  
editado Ago 29 por CICERO FILHO

Assumindo que temos duas funções

\(f\left(n\right)\) e \(g\left(n\right)\)

Se:

\[ \underset{n\to \infty}{\mathrm{lim}} \frac{f\left(n\right)}{g\left(n\right)}=0\]

Assim, \(f\left(n\right) \in\ \vartheta (g\left(n\right))\)

Se:

\[ \underset{n\to \infty}{\mathrm{lim}} \frac{f\left(n\right)}{g\left(n\right)}=c>0\]

Logo, \(f\left(n\right) \in\ \vartheta (g\left(n\right))\) onde c é alguma constante.

Se:

\( \underset{n\to \infty}{\mathrm{lim}} \frac{f\left(n\right)}{g\left(n\right)}=\infty\)

Assim, \(f\left(n\right) \in\ \Omega (g\left(n\right))\).

Assumindo que \(f(n)=log\ n!\) e \(g(n)=n\ log\ n\). Assim, é preciso provar que \( \underset{n\to \infty}{\mathrm{lim}} \frac{f\left(n\right)}{g\left(n\right)}=c>0\), onde c é uma constante.

\[ \underset{n\to \infty}{\mathrm{lim}} \frac{f\left(n\right)}{g\left(n\right)}=\underset{n\to \infty}{\mathrm{lim}} \frac{log\ n!}{n\log\ (n)}\]

\[log\ (n!)=log(1\times2\times3\times...\times n)=\ log(1) + log(2) + log(3)...+ log(n)=\]

\[\sum\ _{i=1} ^{n} log\ (i) \approx \int_{1}^{n} log(x) \,dx \]

\[= [x\ log(x)-x]_1 ^n\]

Utilizando integração por partes, de forma a possibilitar que a integral de um produto seja expressa em outra integral.

\[= n \ log(n) - n + 1 \approx n\ log(n) - n\]

Então,

\[ \underset{n\to \infty}{\mathrm{lim}} \frac{log\ (n!)}{n\log\ (n)} \approx \frac{n\ log\ (n) - n}{n\log\ (n)} \]

\[=1 -\underset{n\to \infty}{\mathrm{lim}} \frac{1}{log\ (n)} = 1\]

Que é constante!

Portanto, é possível concluir que:

\[f\left(n\right) \in\ \Theta (g\left(n\right))\]

ou

\[ log\ n! \in\ \Theta (n\ log\ n).\]

Dessa forma, quando n se aproxima do infinito, n! pode ser substituído pela aproximação de Stirling.

\[n!\sim\ \sqrt{2\pi n}\ \left(\frac{n}{e}\right)^n\]

...