 下界与随机化快速排序式解法)
文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本篇技术指南以《算法导论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. 关键观察问题等价于「三值比较下的排列识别」在进入三道子问之前先建立两个贯穿全题的核心观察这也是原文档推理的立足点解的形式是一一配对由于容量相等关系是红蓝之间的一一对应双射配对结果完全由「蓝壶相对红壶的排列」刻画——把红壶按某个顺序排好蓝壶的某个排列 $\pi$ 即表示「第 $\pi(i)$ 个蓝壶与第 $i$ 个红壶容量相等」。每次比较返回三值一次红蓝比较的结果是「小于 / 等于 / 大于」三种之一这与比较排序中只有「小于 / 大于」两种结果的二叉树模型不同决策树的分支因子是 3。这一点直接决定了下界证明的构造见第 4 节。观察 1 说明可行解的个数恰好是 $n!$蓝壶的排列数观察 2 说明任何算法在单次比较后最多只能区分 3 种情况。这两点分别是下界证明中「叶子数下界」与「树高下界」的来源。3. 问题 a确定性 Θ(n²) 贪心配对算法原文档给出的确定性算法非常朴素选一个红壶与蓝壶逐一比较直到找到容量相等的那只把这组配对放到一边再对下一个红壶重复。算法流程n 轮迭代第 i 轮开始时剩余 $n-i1$ 只蓝壶取一只未配对的红壶 $r$依次与剩余蓝壶比较记录每次结果直至找到唯一的「等于」将 $(r, b)$ 移出集合重复直至所有 $n$ 对配齐。正确性由「每个红壶恰有一只容量相等的蓝壶」保证第 2 步必然在有限次比较内终止第 4 轮之后剩余的一红一蓝必然相等无需再比较。比较次数设第 $i$ 轮配第 $i$ 对$1 \le i \le n-1$开始时剩余 $n-i1$ 只蓝壶最坏情况下要试到最后一只才命中因此第 $i$ 轮最多 $n-i1$ 次比较对前 $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-QUICKSORT5.1 算法描述原文档指出直接采用与随机化快速排序$\text{RANDOMIZED-QUICKSORT}$同构的分治策略随机选取一只蓝壶 $b^*$ 作为 pivot用 $b^$ 依次比较所有红壶将红壶划分为「小于 $b^$」「等于 $b^$」「大于 $b^$」三组——比较过程中必然恰好找到那只与 $b^$ 容量相等的红壶 $r^$再用 $r^$ 依次比较所有蓝壶除 $b^$ 自身外把蓝壶划分为「小于 $r^$」「等于 $r^$」「大于 $r^*$」三组配对 $(r^, b^)$对「小于组」和「大于组」分别递归执行同样的过程。按原文档的记法若恰有 $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_{k1}^{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-i1}$。对所有壶对求和参见 docs/Chap07/7.4.md 中 7.4-4 的求和式$$ E[X] \sum_{i1}^{n-1}\sum_{ji1}^{n}\frac{2}{j-i1} \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_{i2}^{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 的三问环环相扣构成比较型算法设计的标准范式子问任务结论依据a确定性算法Θ(n²) 贪心配对逐对扫描蓝壶$\sum_{i1}^{n-1}i n(n-1)/2$b下界证明Ω(n lg n)三叉决策树$3^h \ge n!$与定理 8.1 同构见 docs/Chap08/8.1.mdc随机化算法期望 O(n lg n)、最坏 Θ(n²)与 RANDOMIZED-QUICKSORT 分析同构见 docs/Chap07/7.3.md 与 docs/Chap07/7.4.md值得进一步思考的延伸点原文档未展开读者可自行推演三叉 vs 二叉本题比较返回三值使得决策树分支因子为 3但下界常数仅相差 $\lg 3$ 倍说明「信息论下界」对分支因子的变化并不敏感跨模型迁移水壶问题的分析手法排列计数 决策树 随机化分治可以原样迁移到其他「两类对象互比、同类禁比」的配对/匹配问题上随机化的价值随机化并未改变最坏情况仍是 Θ(n²)但把「对任意输入的坏表现」概率摊薄使期望性能达到下界——这正是第 7.3 节讨论「为何分析随机化算法的期望运行时间」的动机见 docs/Chap07/7.3.md 7.3-1。通过本题可以完整复习三条主线贪心构造上界、决策树证明下界、随机化分治逼近下界——它们正是《算法导论》第二、七、八章递进安排的缩影。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐k-sorted 数组与平均排序CLRS《算法导论》习题 8-5 全解析k 排序、O(n lg k) 堆归并与 Ω(n lg n) 下界k sorted 数组与平均排序CLRS《算法导论》习题 8 5 全解析k 排序、O n lg k 堆归并与 Ω n lg n 下界 本文围绕 CLRS《文档教程教育CLRS 第 8.1 节习题精解决策树模型与比较排序的 Ω(n lg n) 下界CLRS 第 8.1 节习题精解决策树模型与比较排序的 Ω n lg n 下界 导读本文基于本仓库 C08 Sorting in Linear Time/8文档教程示例工程CLRS 第 8.1 节精读用决策树证明比较排序的 Ω(n lg n) 下界——排序问题习题详解CLRS 第 8.1 节精读用决策树证明比较排序的 Ω n lg n 下界——排序问题习题详解 本篇基于 CLRSIntroduction to Algor文档教程教育创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本篇技术指南以《算法导论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. 关键观察问题等价于「三值比较下的排列识别」在进入三道子问之前先建立两个贯穿全题的核心观察这也是原文档推理的立足点解的形式是一一配对由于容量相等关系是红蓝之间的一一对应双射配对结果完全由「蓝壶相对红壶的排列」刻画——把红壶按某个顺序排好蓝壶的某个排列 $\pi$ 即表示「第 $\pi(i)$ 个蓝壶与第 $i$ 个红壶容量相等」。每次比较返回三值一次红蓝比较的结果是「小于 / 等于 / 大于」三种之一这与比较排序中只有「小于 / 大于」两种结果的二叉树模型不同决策树的分支因子是 3。这一点直接决定了下界证明的构造见第 4 节。观察 1 说明可行解的个数恰好是 $n!$蓝壶的排列数观察 2 说明任何算法在单次比较后最多只能区分 3 种情况。这两点分别是下界证明中「叶子数下界」与「树高下界」的来源。3. 问题 a确定性 Θ(n²) 贪心配对算法原文档给出的确定性算法非常朴素选一个红壶与蓝壶逐一比较直到找到容量相等的那只把这组配对放到一边再对下一个红壶重复。算法流程n 轮迭代第 i 轮开始时剩余 $n-i1$ 只蓝壶取一只未配对的红壶 $r$依次与剩余蓝壶比较记录每次结果直至找到唯一的「等于」将 $(r, b)$ 移出集合重复直至所有 $n$ 对配齐。正确性由「每个红壶恰有一只容量相等的蓝壶」保证第 2 步必然在有限次比较内终止第 4 轮之后剩余的一红一蓝必然相等无需再比较。比较次数设第 $i$ 轮配第 $i$ 对$1 \le i \le n-1$开始时剩余 $n-i1$ 只蓝壶最坏情况下要试到最后一只才命中因此第 $i$ 轮最多 $n-i1$ 次比较对前 $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-QUICKSORT5.1 算法描述原文档指出直接采用与随机化快速排序$\text{RANDOMIZED-QUICKSORT}$同构的分治策略随机选取一只蓝壶 $b^*$ 作为 pivot用 $b^$ 依次比较所有红壶将红壶划分为「小于 $b^$」「等于 $b^$」「大于 $b^$」三组——比较过程中必然恰好找到那只与 $b^$ 容量相等的红壶 $r^$再用 $r^$ 依次比较所有蓝壶除 $b^$ 自身外把蓝壶划分为「小于 $r^$」「等于 $r^$」「大于 $r^*$」三组配对 $(r^, b^)$对「小于组」和「大于组」分别递归执行同样的过程。按原文档的记法若恰有 $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_{k1}^{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-i1}$。对所有壶对求和参见 docs/Chap07/7.4.md 中 7.4-4 的求和式$$ E[X] \sum_{i1}^{n-1}\sum_{ji1}^{n}\frac{2}{j-i1} \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_{i2}^{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 的三问环环相扣构成比较型算法设计的标准范式子问任务结论依据a确定性算法Θ(n²) 贪心配对逐对扫描蓝壶$\sum_{i1}^{n-1}i n(n-1)/2$b下界证明Ω(n lg n)三叉决策树$3^h \ge n!$与定理 8.1 同构见 docs/Chap08/8.1.mdc随机化算法期望 O(n lg n)、最坏 Θ(n²)与 RANDOMIZED-QUICKSORT 分析同构见 docs/Chap07/7.3.md 与 docs/Chap07/7.4.md值得进一步思考的延伸点原文档未展开读者可自行推演三叉 vs 二叉本题比较返回三值使得决策树分支因子为 3但下界常数仅相差 $\lg 3$ 倍说明「信息论下界」对分支因子的变化并不敏感跨模型迁移水壶问题的分析手法排列计数 决策树 随机化分治可以原样迁移到其他「两类对象互比、同类禁比」的配对/匹配问题上随机化的价值随机化并未改变最坏情况仍是 Θ(n²)但把「对任意输入的坏表现」概率摊薄使期望性能达到下界——这正是第 7.3 节讨论「为何分析随机化算法的期望运行时间」的动机见 docs/Chap07/7.3.md 7.3-1。通过本题可以完整复习三条主线贪心构造上界、决策树证明下界、随机化分治逼近下界——它们正是《算法导论》第二、七、八章递进安排的缩影。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐k-sorted 数组与平均排序CLRS《算法导论》习题 8-5 全解析k 排序、O(n lg k) 堆归并与 Ω(n lg n) 下界k sorted 数组与平均排序CLRS《算法导论》习题 8 5 全解析k 排序、O n lg k 堆归并与 Ω n lg n 下界 本文围绕 CLRS《文档教程教育CLRS 第 8.1 节习题精解决策树模型与比较排序的 Ω(n lg n) 下界CLRS 第 8.1 节习题精解决策树模型与比较排序的 Ω n lg n 下界 导读本文基于本仓库 C08 Sorting in Linear Time/8文档教程示例工程CLRS 第 8.1 节精读用决策树证明比较排序的 Ω(n lg n) 下界——排序问题习题详解CLRS 第 8.1 节精读用决策树证明比较排序的 Ω n lg n 下界——排序问题习题详解 本篇基于 CLRSIntroduction to Algor文档教程教育创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考