Chủ đề này có 2 trả lời

[Ispectorgadget]

Chứng minh $n\log n$ là $O(\log n!)$.

[Mrnhan]

Chứng minh $n\log n$ là $O(\log n!)$.

 

Lời giải.

 

$$\log\left ( n! \right )=\sum_{i=1}^{n}\log (i)>\sum_{i=\left \lfloor \frac{n}{2} \right \rfloor+1}^{n}\log(i)>\sum_{i=\left \lfloor \frac{n}{2} \right \rfloor+1}^{n}\log\left(\left \lfloor \frac{n}{2} \right \rfloor + 1\right)$$

 

$$=\left ( n-\left \lfloor \frac{n}{2} \right \rfloor \right )\log\left ( \left \lfloor \frac{n}{2} \right \rfloor+1 \right )>\frac{n}{2}\log\left ( \frac{n}{2} \right )\geq\frac{n}{4}\log(n), \, \forall n \geq 4$$

 

Từ đó suy ra điều cần phải chứng minh

[DOTOANNANG]

$$\lg n!= \Theta\left ( n\lg n \right )$$

Giải.

Dùng xấp xỉ Stirling, có được

$$\lg n!= \lg\left ( \sqrt{2\pi n}\left ( \frac{n}{e} \right )^{n}\left ( 1+ \Theta\left ( \frac{1}{n} \right ) \right ) \right )= \frac{1}{2}\lg\left ( 2\pi n \right )+ n\lg n- n\lg e+ \lg\left ( \Theta\left ( \frac{n+ 1}{n} \right ) \right )$$

Mặt khác

$$\lg\left ( \Theta\left ( \frac{n+ 1}{n} \right ) \right )\ll\lg n\ll n\lg n\;{\rm as}\,n\rightarrow\infty\Leftarrow\lg\left ( \frac{n+ 1}{n} \right )\leq\lg\left ( n+ 1 \right )+ \lg n= \mathcal{O}\left ( \lg n \right )$$

Bài viết đã được chỉnh sửa nội dung bởi DOTOANNANG: 29-06-2021 - 15:49