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

发表于 分类于 阅读次数：

  这是离散数学中一道关于算法渐进复杂度的证明题：求证 $\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)$

∵ ∀n>0, log⁡2n!≤log⁡2nn=nlog⁡2n∴ log⁡2n!∈O(nlog⁡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)$

∵ n!≥(n2)n2∴ log⁡2n!≥log⁡2(n2)n2=n2log⁡2n2=n2log⁡2n−n2log⁡22∵ ∀n>4, n2log⁡22=n4log⁡24<n4log⁡2n∴ ∀n>4, log⁡2n!≥n2log⁡2n−n4log⁡2n=14nlog⁡2n∴ log⁡2n!∈Ω(nlog⁡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)$ 。