排序不等式 | 微扰法

摘要: 排序不等式

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

---

各位好，后续我们将讨论一些贪心算法的问题。由基础算法方面的知识我们知道，对于一个优化问题，贪心算法要想成立，需要证明两件事，一个是最优子结构、一个是贪心选择性质。

对于最优子结构来讲，证明路径比较清晰，就是看问题的最优解是否包含了子问题的最优解，比较流程化，在《算法导论》中称为 cut-and-paste 方法，动态规划算法也是需要这一步的。

贪心选择性质是指按照贪心策略可以得到最优解，这一步论证比较灵活，没有通用的方法，一些常见的方法有微扰、邻项交换、决策包容性、范围缩放、反证法、数学归纳法等。

上述这些证明贪心选择性质的方法或多或少涉及到一些不等式的内容。本文来看一个很基础的不等式：排序不等式。排序不等式的证明过程比较初等，但体现了微扰的思想，这也是贪心论证的常用思想。

排序不等式

设 $a_{1} \leq a_{2} \leq \cdots \leq a_{n}$，$b_{1} \leq b_{2} \leq \cdots \leq b_{n}$ 为两个长度为 $n$ 的数列。$k_{1},\cdots,k_{n}$ 为 $\{1,2,\cdots,n\}$ 的任意排列。则成立以下两个不等式：

$$\sum\limits_{j=1}\limits^{n}a_{j}b_{n+1-j} \leq \sum\limits_{j=1}\limits^{n}a_{j}b_{k_{j}} \leq \sum\limits_{j=1}\limits^{n}a_{j}b_{j}$$ $$\prod\limits_{j=1}\limits^{n}a_{j}^{b_{n+1-j}} \leq \prod\limits_{j=1}\limits^{n}a_{j}^{b_{k_{j}}} \leq \prod\limits_{j=1}\limits^{n}a_{j}^{b_{j}}$$

---

该不等式称为排序不等式，是因为可以直观理解为：【反序和 $\leq$ 乱序和 $\leq$ 同序和】。在一些算法问题中，涉及到从数组中取元素进行处理，每个元素取一次，选取顺序决定结果的场景，排序不等式可能会诱导出贪心算法。

该不等式也是高中数学竞赛中经常登场的不等式，证明过程是初等的，体现了微扰的思想。以下我们仅以第一个不等式的右半部分为例，即 $\sum\limits_{j=1}\limits^{n}a_{j}b_{k_{j}} \leq \sum\limits_{j=1}\limits^{n}a_{j}b_{j}$，给出证明，另外三个部分的证明过程完全类似。

证明（微扰法）

令 $S_{n} = \sum\limits_{j=1}\limits^{n}a_{j}b_{k_{j}}$，我们要证的是当 $k_{j} = j$，$(j = 1,2,\cdots,n)$ 时，$S_{n}$ 取最大值 $\sum\limits_{j=1}\limits^{n}a_{j}b_{j}$。

若 $k_{n} \neq n$ 则存在某个 $j_{0} \neq n$ 使得 $b_{n}$ 与 $a_{j_{0}}$ 搭配，于是：

$$a_{n}b_{n} + a_{j_{0}}b_{k_{n}} - (a_{n}b_{k_{n}} + a_{j_{0}}b_{n}) = (b_{n} - b_{k_{n}})(a_{n} - a_{j_{0}}) \geq 0$$

即：

$$a_{n}b_{k_{n}} + a_{j_{0}}b_{n} \leq a_{n}b_{n} + a_{j_{0}}b_{k_{n}}$$

上式说明，$k_{n} \neq n$ 时，交换 $S_{n}$ 中 $b_{n}$ 与 $b_{k_{n}}$ 的位置，会使得 $S_{n}$ 增加。

依次类推，可以证明 $a_{k}$ 与 $b_{k}$ 搭配时，$S_{n}$ 最大。

$\Box$

总结

此前在文章 概率方法的威力：由数学期望的性质推导出不等式 中，我们通过概率方法证明了一个长为 $n$ 的数列成立以下不等式：

$$\frac{1}{n}(\sum\limits_{i=1}^{n}w_{i})^{2} \leq \sum\limits_{i=1}\limits^{n}w_{i}^{2}$$

将以上不等式推广一下就是两个长为 $n$ 的数列成立以下不等式，称为切比雪夫总和不等式。该不等式的描述如下。

设 $a_{1} \leq a_{2} \leq \cdots \leq a_{n}$，$b_{1} \leq b_{2} \leq \cdots \leq b_{n}$ 为两个长度为 $n$ 的数列。则有以下不等式：

$$(\sum\limits_{i=1}\limits^{n}a_{i})(\sum\limits_{i=1}\limits^{n}b_{i}) \leq n(\sum\limits_{i=1}\limits^{n}a_{i}b_{i})$$

而切比雪夫总和不等式再一推广，就是本文介绍的排序不等式。

由上述推广关系，从排序不等式出发，自然可以先证明切比雪夫总和不等式、然后再进一步证明第一个不等式。

此外从排序不等式出发，还可以证明几何-算术平均不等式、柯西不等式。而排序不等式是通过微扰法证明的，没有循环论证的问题。

---