基于比较的排序算法的时间复杂度

记录一种使用信息熵证明基于比较的排序算法的时间复杂度下限为$\Omega (n\log n)$的方法。

信息熵的计算方法为：

$$H(X) =- \sum_{i=1}^{n} P(X=i) \log_2P(X=i)$$

对于一个含有$n$个不同元素的数列，令随机变量$X$表示数列的排列顺序。易知数列总共有$n!$种不同的排列方法。因此，有$\forall i, P(X=i) = \frac{1}{n!}$。故对于一个乱序数列，其信息熵为

$$H(X) = -n! \cdot \frac{1}{n!} \cdot \log_2 \frac{1}{n!} = \log_2 (n!) \text{ bit}$$

接下来计算每次比较大小获得的信息增益。不妨设某时刻数列有$m$种排列的可能，经过一次比较大小，数列中的一对元素确定了先后顺序，此时的数列可能的排列总数变为$\frac{m}{2}$。设比较大小的两种结果（即大于或小于）的概率分别为$p$和$1-p$，则有

$$I(Y,X) = H(X) - H(X|Y) = \log_2 m - p\cdot \log_2 \frac{m}2 - (1-p) \cdot \log_2\frac{m}{2} = 1 \text{ bit}$$

由斯特林公式：

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

可得总比较次数最少为：

$$\begin{align} \frac{H(X)}{I(Y,X)}& = \log_2(n!)\\ &\approx \log_2\left( \sqrt{2\pi n}\left(\frac{n}{e}\right)^n \right)\\ &= \log_2\sqrt{2\pi n} + n\log_2n - n\log_2 e\\ &= \Omega (n\log n) \end{align}$$