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

Eficiência de Algoritmos

0 votos
16 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\]

...