企业官网建设流程全解析

• 文档
• 教程
• 教育

本篇技术指南以《算法导论（Introduction to Algorithms）》第三版第 8 章问题 8-4「水壶配对问题」为对象，基于本仓库 docs/Chap08/Problems/8-4.md 的官方习题解答展开，完整梳理三道子问题：先给出比较次数为 Θ(n²) 的确定性贪心配对算法，再借助决策树证明任何算法都至少需要 Ω(n lg n) 次比较，最后给出期望比较次数为 O(n lg n)、最坏情况 Θ(n²) 的随机化分治算法，并证明其期望上界。读完本篇，你将掌握如何把一个「跨颜色比较」的配对问题归约为比较排序式的决策树分析，以及如何把 RANDOMIZED-QUICKSORT 的期望分析思想迁移到非排序问题上。

1. 问题背景与数学模型

原题出自 CLRS 第 8 章「Sorting in Linear Time」末尾的问题集（Problem 8-4），在仓库导航 mkdocs.yml 中登记为8-4 Water jugs: Chap08/Problems/8-4.md。

问题设定：给定 $n$ 个红壶和 $n$ 个蓝壶，所有壶形状、大小各异；红壶之间容量互不相同，蓝壶之间容量也互不相同，并且每个红壶恰好存在一个容量相等的蓝壶（反之亦然）。任务是找出把红蓝壶配成容量相等的一一对应分组。

允许的操作：只能「红壶 × 蓝壶」配对比较——任取一个红壶和一个蓝壶，把红壶装满水倒入蓝壶，即可判定红壶容量大于、小于或等于蓝壶。该比较计 1 个时间单位。不允许直接比较两个红壶或两个蓝壶。

目标：设计使用比较次数尽量少的算法来确定完整配对。

题目进一步拆成三个递进子问（原文档原文）：

• a.描述一个使用 $\Theta(n^2)$ 次比较完成配对的确定性算法；
• b.证明解决该问题的任何算法比较次数下界为 $\Omega(n\lg n)$；
• c.给出一个期望比较次数为 $O(n\lg n)$ 的随机化算法并证明该界正确，同时说明其最坏情况比较次数。

注意本仓库及原书采用 $\lg$ 表示以 2 为底的对数。第 8 章的核心主题是「比较排序的下界 $\Omega(n\lg n)$」（参见仓库 docs/Chap08/8.1.md），本题正是把这一下界思想推广到非排序的比较型配对问题。

2. 关键观察：问题等价于「三值比较下的排列识别」

在进入三道子问之前，先建立两个贯穿全题的核心观察，这也是原文档推理的立足点：

1. 解的形式是一一配对：由于容量相等关系是红蓝之间的一一对应（双射），配对结果完全由「蓝壶相对红壶的排列」刻画——把红壶按某个顺序排好，蓝壶的某个排列 $\pi$ 即表示「第 $\pi(i)$ 个蓝壶与第 $i$ 个红壶容量相等」。
2. 每次比较返回三值：一次红蓝比较的结果是「小于 / 等于 / 大于」三种之一，这与比较排序中只有「小于 / 大于」两种结果的二叉树模型不同，决策树的分支因子是 3。这一点直接决定了下界证明的构造（见第 4 节）。

观察 1 说明可行解的个数恰好是 $n!$（蓝壶的排列数）；观察 2 说明任何算法在单次比较后最多只能区分 3 种情况。这两点分别是下界证明中「叶子数下界」与「树高下界」的来源。

3. 问题 a：确定性 Θ(n²) 贪心配对算法

原文档给出的确定性算法非常朴素：

选一个红壶，与蓝壶逐一比较直到找到容量相等的那只；把这组配对放到一边，再对下一个红壶重复。

算法流程（n 轮迭代，第 i 轮开始时剩余 $n-i+1$ 只蓝壶）：

1. 取一只未配对的红壶 $r$；
2. 依次与剩余蓝壶比较，记录每次结果，直至找到唯一的「等于」；
3. 将 $(r, b)$ 移出集合；
4. 重复直至所有 $n$ 对配齐。

正确性：由「每个红壶恰有一只容量相等的蓝壶」保证第 2 步必然在有限次比较内终止；第 4 轮之后剩余的一红一蓝必然相等，无需再比较。

比较次数：设第 $i$ 轮（配第 $i$ 对，$1 \le i \le n-1$）开始时剩余 $n-i+1$ 只蓝壶，最坏情况下要试到最后一只才命中，因此第 $i$ 轮最多 $n-i+1$ 次比较；对前 $n-1$ 轮求和（最后一轮无需比较）得：

$$ \sum_{i = 1}^{n - 1} i = \frac{n(n - 1)}{2} = \Theta(n^2). $$

原文档明确给出该结论："This will use at most $\sum_{i = 1}^{n - 1} i = n(n - 1) / 2 = \Theta(n^2)$ comparisons."该算法的优点是实现简单、确定性、绝不依赖随机源，代价是与 $n$ 呈平方关系，在 $n$ 较大时开销过高，这为后面的下界与优化算法埋下伏笔。

4. 问题 b：决策树证明 Ω(n lg n) 比较下界

这一问是本题的理论核心。原文档采用与第 8.1 节「排序的下界」（定理 8.1）完全一致的决策树论证（可对照仓库 docs/Chap08/8.1.md 中 8.1-3 对 $\lg(n!)$ 与树高的处理）：

决策树模型：

• 先把红壶按某个固定顺序排列好；
• 一个可行解 = 蓝壶的一个排列，使第 $i$ 个蓝壶与第 $i$ 个红壶容量相等；
• 决策树内部节点代表「某只特定红壶 × 某只特定蓝壶」的一次比较；
• 由于比较结果是「大于 / 小于 / 等于」三种，每个内部节点有 3 个孩子（三叉决策树）；
• 叶子节点代表依据比较结果序列确定的蓝壶排列。

叶子数下界：必须区分 $n!$ 种不同的排列（每种排列对应一种容量对应关系），因此至少需要 $n!$ 片叶子。

树高下界：三叉树高度为 $h$ 时最多有 $3^h$ 片叶子，故

$$ 3^h \ge n! \quad\Longrightarrow\quad h \ge \log_3(n!) . $$

又由斯特林近似或更初等的估计 $\log_3(n!) \ge \log_3\left((n/2)^{n/2}\right) = \Theta(n\lg n)$（常数因子 $\frac{1}{\lg 3}$ 被 $\Theta$ 吸收），得到

$$ h = \Omega(n\lg n). $$

结论：由于一次执行对应决策树中一条根到叶的简单路径，任何能正确输出配对的算法，其最坏情况比较次数都至少是树高，即 $\Omega(n\lg n)$。原文档表述为："Since a solution corresponds to a simple path from root to leaf, an algorithm must make at least $\Theta(n\lg n)$ comparisons to reach any leaf."

值得强调的细节是：虽然本题的比较有 3 种结果、树是三叉的（而比较排序的树是二叉的），但渐近下界不变——三叉只是把常数因子从 $\frac{1}{\lg 3}$ 略微缩小，$\Theta$ 记号下仍是 $\Omega(n\lg n)$。这说明 $\Theta(n^2)$ 的贪心算法离最优还很远，也印证了第 8 章「基于比较的归约问题都逃不出 $n\lg n$ 这道门槛」的核心思想。

5. 问题 c：随机化算法——水壶版的 RANDOMIZED-QUICKSORT

5.1 算法描述

原文档指出，直接采用与随机化快速排序（$\text{RANDOMIZED-QUICKSORT}$）同构的分治策略：

1. 随机选取一只蓝壶 $b^*$ 作为 pivot；
2. 用 $b^$ 依次比较所有红壶，将红壶划分为「小于 $b^$」「等于 $b^$」「大于 $b^$」三组——比较过程中必然恰好找到那只与 $b^$ 容量相等的红壶 $r^$；
3. 再用 $r^$ 依次比较所有蓝壶（除 $b^$ 自身外），把蓝壶划分为「小于 $r^$」「等于 $r^$」「大于 $r^*$」三组；
4. 配对 $(r^, b^)$；
5. 对「小于组」和「大于组」分别递归执行同样的过程。

按原文档的记法：若恰有 $k$ 只红壶「不大于」pivot（其中 $k-1$ 只严格小于、1 只等于），则需要在规模为 $k-1$（严格小于部分）和 $n-k$（严格大于部分）的两个子问题上继续求解——$k-1 + (n-k) = n-1$ 恰是排除 pivot 对后的剩余壶数。规模为 1 的子问题是平凡的：只剩一只红壶和一只蓝壶时，它们必然容量相等。

伪代码可整理如下：

WATER-JUGS(R, B) if |R| == 1: return { (R[0], B[0]) } // 一红一蓝，必相等 b* = B[RANDOM(1, |B|)] // 随机选蓝壶 pivot (R_less, r*, R_greater) = PARTITION_RED(R, b*) // 与 b* 比较每只红壶：小于 / 等于(恰一只) / 大于 (B_less, b*, B_greater) = PARTITION_BLUE(B, r*) // 与 r* 比较每只蓝壶：小于 / 等于(即 b*) / 大于 return { (r*, b*) } ∪ WATER-JUGS(R_less, B_less) ∪ WATER-JUGS(R_greater, B_greater)

该结构与仓库 docs/Chap07/7.3.md 描述的 $\text{RANDOMIZED-QUICKSORT}$（随机选 pivot + 划分 + 递归）完全同构，区别仅在于：本题每一层要做两轮划分（先蓝 pivot 划分红壶，再红 pivot 划分蓝壶），且最终找到的「相等元素」被单独取出不再参与递归。

5.2 期望比较次数 O(n lg n) 的证明

原文档直接给出论证路径："The analysis of expected number of comparisons is exactly the same as that of $\text{RANDOMIZED-QUICKSORT}$ given on pages 181-184."仓库中对应的期望分析见 docs/Chap07/7.4.md（其 7.4-4 给出了 $\text{RANDOMIZED-QUICKSORT}$ 期望比较次数的完整推导）。

展开来说，设 $E[T(n)]$ 为规模 $n$ 的期望比较次数。随机 pivot 在红壶中的秩 $k$ 在 $1..n$ 上均匀分布，递归式形如

$$ E[T(n)] = \frac{1}{n}\sum_{k=1}^{n}\big(E[T(k-1)] + E[T(n-k)]\big) + \Theta(n), $$

这与 $\text{RANDOMIZED-QUICKSORT}$ 的期望递推完全相同，解为 $E[T(n)] = O(n\lg n)$。其本质（指标随机变量分析）是：对容量排名第 $i$ 小与第 $j$ 小（$i < j$）的一对红蓝壶，它们在整个执行中被比较，当且仅当两者同处一个尚未被更小/更大的 pivot 分隔的子问题、且其中之一恰好被选为该子问题的 pivot，概率为 $\frac{2}{j-i+1}$。对所有壶对求和（参见 docs/Chap07/7.4.md 中 7.4-4 的求和式）：

$$ E[X] = \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\frac{2}{j-i+1} = \Theta(n\lg n). $$

本题的特殊之处在于每层要做两轮划分（红侧一轮、蓝侧一轮），因此期望比较次数大约翻倍——但这只是一个常数因子，被大 $O$ 记号吸收，最终结论不变。原文档表述为："We are running the procedure twice so the expected number of comparisons is doubled, but this is absorbed by the big-$O$ notation."由此证明期望上界 $O(n\lg n)$ 正确，并与第 4 节的下界 $\Omega(n\lg n)$ 匹配——期望意义下该随机化算法渐近最优。

5.3 最坏情况分析

最坏情况与快速排序如出一辙：每次随机选出的 pivot 恰好都是当前子问题中容量最大的蓝壶（或每次都排到最大一侧）。此时：

• 划分红壶需要与全部 $n$ 只红壶比较（其中 $n-1$ 次结果为「小于」，1 次为「等于」）；
• 划分蓝壶需要与除 pivot 外的 $n-1$ 只蓝壶比较；
• 合计 $2n-1$ 次比较，剩余子问题规模为 $n-1$。

于是 $T(n) = T(n-1) + 2n - 1$，$T(1) = 0$，展开得

$$ T(n) = \sum_{i=2}^{n}(2i-1) = n^2 - 1 = \Theta(n^2). $$

原文档将该式记为 $\sum_{i = 2}^n i + i - 1 = n^2$（精确值为 $n^2 - 1$，渐近意义一致），即最坏情况退化到与问题 a 的确定性算法相同的 $\Theta(n^2)$。这一退化模式与快速排序在「每次划分都极端不平衡」时退化为 $\Theta(n^2)$（参见 docs/Chap07/7.2.md 中 7.2-3 的讨论）完全对应——随机化保证了期望上的平衡，却无法杜绝坏运气。

6. 总结：三道子问构成的完整推理链条

问题 8-4 的三问环环相扣，构成比较型算法设计的标准范式：

值得进一步思考的延伸点（原文档未展开，读者可自行推演）：

• 三叉 vs 二叉：本题比较返回三值使得决策树分支因子为 3，但下界常数仅相差 $\lg 3$ 倍，说明「信息论下界」对分支因子的变化并不敏感；
• 跨模型迁移：水壶问题的分析手法（排列计数 + 决策树 + 随机化分治）可以原样迁移到其他「两类对象互比、同类禁比」的配对/匹配问题上；
• 随机化的价值：随机化并未改变最坏情况（仍是 Θ(n²)），但把「对任意输入的坏表现」概率摊薄，使期望性能达到下界——这正是第 7.3 节讨论「为何分析随机化算法的期望运行时间」的动机（见 docs/Chap07/7.3.md 7.3-1）。

通过本题可以完整复习三条主线：贪心构造上界、决策树证明下界、随机化分治逼近下界——它们正是《算法导论》第二、七、八章递进安排的缩影。

• 文档
• 教程
• 教育