一个算法分析的证明：概率方法证明上下界的范式

摘要: 通过概率方法讨论上下界的方式

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

各位好，今天我们来看一个算法分析中的不起眼的问题，证明过程很简单，但是体现了一种证明的范式，这种范式跟香农信息论中的论述过程有点像，值得看一下。

香农信息论中证明上界的范式

对于研发或算法工程师来说，我们或多或少都了解香农以及他的信息论，他在1948年发表的论文《通信的数学理论》中，通过数学方法研究了通信系统的特性，讨论了通信系统中的核心概念，并推导了一些上下界。

香农的这篇文章贡献非常多，其中的一个点就是在推导信道容量的上界、误码率的上界时，是通过概率的方法展开的，这可以称得上是一种证明的范式，我们通过一个例子说明一下流程。

比如想知道一组人跑1000米时间的下界，如果我们知道这些人跑1000米的平均时间为 4 分钟，那么我就可以说这些人中时间最短的那个肯定不大于 4 分钟，也就是下界肯定不大于 4 分钟。虽然不知道具体是谁，但是我们可以说这些人中至少存在一个人，他的成绩不大于 4 分钟。

在香农的推导过程中就是类似的，比如想要知道信源编码的压缩率的上界是多少，如果能知道所有编码方式的平均压缩率为 $a$，那么就可以说肯定存在一种编码方式，使得其压缩率不小于 $a$，大致上是这样的一个思路。

从此以后，人们恍然大悟，原来可以通过概率的方式对一些上下界进行论述，这是一种范式上的创新。当我们对一个问题的上下界进行讨论时，就多了一个方法可以考虑。

一个算法分析问题

在算法分析中，我们常用的表述有 $O$ 符号、$\Omega$ 符号、$\Theta$ 符号，这些符号均与上下界有关。因此自然就可以引入概率的方法来分析。下面我们看一个问题。

假设我们知道一个算法在平均情况下的时间复杂度为 $\Theta(f(n))$（$\Theta$ 符号同时包含了上界和下界），那么该算法在最坏情况下的时间复杂度至少为 $\Omega(f(n))$ （$\Omega$ 符号表达的是一个下界）。下面我们推导这个事情。

证明

记 $T_{avg}(N)$ 为输入规模为 $N$ 时的平均情况时间复杂度。记所有规模为 $N$ 的输入的集合为 $D_{N}$，对于 $D_{N}$ 中的每个实例 $I$，它出现的概率为 $P(I)$。那么根据 $T_{avg}(N)$ 的定义就有：

$$T_{avg}(N) = \sum\limits_{I\in D_{N}}P(I)T(N, I)$$

其中 $T(N, I)$ 表示对于输入规模为 $N$ 的一个特定输入实例 $I$，该算法的运行时间是多少。记 $I^{*}$ 为规模为 $N$ 的运行时间最大的那个实例，也就是：

$$T(N, I^{* }) = \max\limits_{I' \in D_{N}}T(N, I')$$

那么自然就有 $T(N, I) \leq T(N, I^{*})$，根据定义 $T(N, I^{*})$ 即为最坏情况的时间复杂度，记为 $T_{max}(N)$，于是：

$$\begin{align} T_{avg}(N) &= \sum\limits_{I\in D_{N}}P(I)T(N, I) \\ &\leq \sum\limits_{I\in D_{N}}P(I)T(N, I^{* }) \\ &= T(N, I^{* })\sum\limits_{I\in D_{N}}P(I) \\ &= T(N, I^{* }) \\ &= T_{max}(N) \end{align}$$

也就是说，最坏情况的时间复杂度至少不小于平均情况的时间复杂度，即 $T_{max}(N) \geq T_{avg}(N)$。于是：

$$T_{max}(N) = \Omega(T_{avg}(N)) = \Omega(\Theta(f(n))) = \Omega(f(n))$$

$\Box$

总结

本文我们证明了算法分析中的一个比较显然的命题，即一个算法的最坏情况时间复杂度至少不小于平均情况的时间复杂度。推导过程非常直接，高中数学即可搞定。

问题本身很简单，但值得注意的是这竟然与香农在信息论中推导的一些上界在思路上是一样的。

---