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

记录一种使用信息熵证明基于比较的排序算法的时间复杂度下限为\(\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} \]