证明两种线性对数阶复杂度的表示方法等价

  这是离散数学中一道关于算法渐进复杂度的证明题：求证 $\log_2n!\in\Theta(n\log_2n)$ 。
  看了网上的一些证明，大多借助斯特林公式，即 $\lim\limits_{n\to+\infty}\frac{n!}{\sqrt{2\pi n}(\frac ne)^n}=1$ ，将 $n!$ 替换成同阶的 $\sqrt{2\pi n}(\frac ne)^n$ 进行证明。若不熟悉该公式，很难想到这种等价替换。在此给出一种比较朴素的证明方法。

证明分两部分：
1. 先证 $\log_2n!\in O(n\log_2n)$

$$\begin{aligned} &∵\ ∀n\gt0,\ \log_2n!\le \log_2n^n=n\log_2n \\ &∴\ \log_2n!\in O(n\log_2n) \end{aligned}$$

2. 再证 $\log_2n!\in \Omega(n\log_2n)$

$$\begin{aligned} &∵\ n!\ge (\frac n2)^\frac n2 \\ &∴\ \log_2n!\ge\log_2(\frac n2)^\frac n2=\frac n2\log_2\frac n2=\frac n2\log_2n-\frac n2\log_22 \\ &∵\ ∀n\gt4,\ \frac n2\log_22=\frac n4\log_24\lt\frac n4\log_2n \\ &∴\ ∀n\gt4,\ \log_2n!\ge\frac n2\log_2n-\frac n4\log_2n=\frac 14n\log_2n \\ &∴\ \log_2n!\in \Omega(n\log_2n) \end{aligned}$$

综上所述， $\log_2n!\in\Theta(n\log_2n)$ 。