文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载导读本文以 CLRS 解题仓库的 7.3 小节解答 为核心骨架完整继承并深入展开《算法导论第三版》第 7.3 节快速排序的随机化版本的两道习题其一回答为什么随机化算法要分析期望运行时间而非最坏情况运行时间其二用递推式定量求解 RANDOMIZED-QUICKSORT 对随机数生成器 RANDOM 的调用次数。在此基础上文章进一步串联第 7 章的 7.1、7.2、7.4 与 Problems 7-2、7-3、7-5 解答把随机化 → 期望分析 → Θ(n lg n)这条主线讲透。1. 背景确定性快速排序的软肋在进入随机化版本之前先明确它要解决的问题。第 7.1 节的PARTITION过程以子数组末尾元素A[r]为主元一趟扫描把数组分成小于等于主元与大于主元两部分其运行时间对规模为 $n$ 的子数组是 $\Theta(n)$见 7.1-3 解答 之前的 7.1.md。问题出在第 7.2 节指出的最坏情况当输入恰好是已排序升序或降序数组、或所有元素相同时每次PARTITION都产出一个空分区和一个规模 $n-1$ 的分区递推式$$T(n) T(n-1) \Theta(n)$$的解是 $\Theta(n^2)$7.2-1、7.2-2、7.2-3 解答。也就是说一个对绝大多数输入都很快的算法会被少量坏输入直接拖垮——而且这类坏输入在现实数据如按时间戳记录的银行流水、几乎有序的集合中并不罕见。随机化版本的思路由此而来不让输入决定主元而让随机数生成器决定主元。2. 随机化机制RANDOMIZED-PARTITION 与 RANDOMIZED-QUICKSORT教材 7.3 节的标准做法是在PARTITION之前先用RANDOM(p, r)从区间 $[p, r]$ 中均匀随机地选出一个下标把该位置元素与A[r]交换再执行原有的PARTITION过程。即RANDOMIZED-PARTITION(A, p, r) i RANDOM(p, r) exchange A[r] with A[i] return PARTITION(A, p, r) RANDOMIZED-QUICKSORT(A, p, r) if p r q RANDOMIZED-PARTITION(A, p, r) RANDOMIZED-QUICKSORT(A, p, q - 1) RANDOMIZED-QUICKSORT(A, q 1, r)这一结构的正确性在仓库中可以从两个方向得到印证问题 7-1Hoare 划分 讨论了与教材 PARTITION 不同的原始划分算法其HOARE-QUICKSORT递归调用HOARE-PARTITION(A, p, q)与HOARE-PARTITION(A, q 1, r)展示了主元处理方式变化时递归骨架的对应调整问题 7-2相等元素 直接以RANDOMIZED-QUICKSORT为讨论对象给出调用RANDOMIZED-PARTITION的QUICKSORT伪代码并指出当元素全相等时RANDOMIZED-QUICKSORT恒返回 $q r$递推式 $T(n) T(n-1) \Theta(n) \Theta(n^2)$。随机化之后主元在 $n$ 个元素中等概率选取最坏情况不再由特定输入唯一决定——这正是下一节习题 7.3-1 的论述起点。3. 习题 7.3-1为什么分析期望运行时间而非最坏情况运行时间题目为什么我们要分析随机化算法的期望运行时间而不分析它的最坏情况运行时间仓库解答7.3.md 第 3-5 行We analyze the expected run time because it represents the more typical time cost. Also, we are doing the expected run time over the possible randomness used during computation because it cant be produced adversarially, unlike when doing expected run time over all possible inputs to the algorithm.这段话包含两个递进的层次期望运行时间刻画典型代价。确定性算法的运行时间完全由输入决定而随机化算法的运行时间还取决于算法内部的随机选择。对随机化算法取期望时我们在随机选择这一维度上做平均得到的是该算法在任意固定输入下、反复运行多次的典型时间成本它比单个最坏情况更能反映实际使用体验。关键差异随机性无法被输入对抗性构造。如果对所有可能输入取期望即平均情况分析输入分布往往是假设的攻击者或特殊数据可以刻意逼近最坏输入让分析失效但随机化算法的期望是针对算法内部抛硬币的结果取平均——输入可以任意选择却无法预先知道并利用随机的落点。正如解答所说这种期望cant be produced adversarially不能被对抗性地制造出来。于是随机化把与输入博弈转化为与概率博弈无论输入多么糟糕只要坏随机序列坏分割的概率足够小算法总体就是高效的。这个小概率坏事件的量化观正是 7.2 节两道星号习题的用武之地7.2-5若每一层分割比例恒为 $1-\alpha$ 对 $\alpha$$0\alpha\le 1/2$递归树叶子最小深度约为 $-\lg n/\lg\alpha$最大深度约为 $-\lg n/\lg(1-\alpha)$——分割越失衡递归越深7.2-6随机主元下得到比 $1-\alpha$ 对 $\alpha$ 更平衡分割的概率约为 $1-2\alpha$主元落入最小 $\alpha n$ 个或最大 $\alpha n$ 个元素的概率各约 $\alpha$合计 $2\alpha$。两题合起来说明随机主元既大概率给出足够平衡的分割如取 $\alpha 1/3$平衡概率约 $1/3$又把失衡情况限制为小概率事件期望代价因此可控。4. 习题 7.3-2RANDOM 调用次数的最坏与最好情况题目当 RANDOMIZED-QUICKSORT 运行时最坏情况下对随机数生成器 RANDOM 调用多少次最好情况呢请用 Θ 记号作答。仓库解答7.3.md 第 9-19 行最坏情况。每次RANDOMIZED-PARTITION恰调用一次RANDOM而每次递归调用又对应一次新的RANDOM调用。最坏情况每次分割产生一个规模 $n-1$ 的子问题和一个空子问题下$$T(n) T(n-1) 1 n \Theta(n).$$最好情况。每次分割恰好对半分两个子问题规模各为 $n/2$$$T(n) 2T(n/2) 1 \Theta(n).$$对后者用主定理情形 1$f(n) 1 O(n^{\lg 2 - \epsilon})$故 $T(n) \Theta(n^{\lg 2}) \Theta(n)$。解答的直观注记原文补充道这并不令人意外因为每个至少第三个元素都会被选为主元。这句话的含义可以从期望层面理解主元在元素序列中等概率随机选取任何元素都不会被系统性跳过递归树节点数即 RANDOM 调用次数在两个极端情形下都只有线性规模。需要强调的结论是RANDOM 调用次数与快速排序本身的运行时间不在一个数量级上。一次RANDOM(p, r)的开销是常数或对数级的即使最坏情况也仅 $\Theta(n)$ 次调用真正主导总运行时间的是每一层分割付出的 $\Theta(n)$ 工作以及随之而来的递归树深度。因此7.3 节的期望分析把注意力放在期望的分割质量上而不是随机数生成的开销上——这一点与 7.4 节的分析 一脉相承。5. 期望运行时间 Θ(n lg n)7.4 分析与问题 7-3 的两条证明路线随机化之后核心定理是RANDOMIZED-QUICKSORT 在任意输入上的期望运行时间为 $\Theta(n\lg n)$。仓库给出了两条完整的证明路线。路线一7.4 节的比较次数期望分析。用指示随机变量刻画元素 $z_i$ 与 $z_j$ 是否被比较利用线性期望可得$$\text E[X] \sum_{i1}^{n-1}\sum_{ji1}^{n}\frac{2}{j-i1} \Theta(n\lg n).$$其中 7.4-4 解答 用不等式放缩给出下界$$\text E[X] \ge \sum_{i1}^{n-1}\sum_{k1}^{n-i}\frac{2}{2k} \Omega(n\lg n),$$从而期望比较次数进而期望运行时间为 $\Theta(n\lg n)$。路线二问题 7-3 的逐次调用分析。它不从比较次数而从每次递归调用的期望时间入手(a)任一特定元素被选为主元的概率为 $1/n$定义 $X_i I{\text{第 } i \text{ 小元素被选为主元}}$则 $\text E[X_i] 1/n$(b)由线性期望得 $\text E[T(n)] \text E\left[\sum_{q1}^{n}X_q(T(q-1)T(n-q)\Theta(n))\right]$式 7.5(c)化简为 $\text E[T(n)] \frac{2}{n}\sum_{q2}^{n-1}\text E[T(q)] \Theta(n)$式 7.6(d)用积分近似证明 $\sum_{k2}^{n-1}k\lg k \le \frac{1}{2}n^2\lg n - \frac{1}{8}n^2$式 7.7(e)代入归纳假设 $\text E[T(q)] \le q\lg q \Theta(n)$最终得到 $\text E[T(n)] \Theta(n\lg n)$。两条路线互为印证前者直接对比较次数求期望后者对运行时间本身建立递推并求解殊途同归地支撑了 7.3 节的结论——随机化让快速排序在任意输入上都有 $\Theta(n\lg n)$ 的期望性能。6. 延伸随机化主元的两种实用改进理解了期望分析的机制再看第 7 章末尾两个随机化变体就水到渠成变体一相等元素场景问题 7-2。若数组含大量重复值标准 RANDOMIZED-QUICKSORT 仍可能退化到 $\Theta(n^2)$元素全相等时 $q r$。解答给出的PARTITION返回两个下标(low, high)把与主元相等的元素集中到 $A[q..t]$ 中间带QUICKSORT只递归两侧严格小于/大于主元的区间。由于不再递归相等元素子问题规模不会超过全异元素情形7.4.2 的分析得以免除元素互异假设。变体二median-of-3 主元问题 7-5。随机取 3 个元素以其中位数为主元。解答推导出第 $i$ 小元素被选中的概率$$p_i \frac{6(n-i)(i-1)}{n(n-1)(n-2)},\quad i 2,3,\ldots,n-1,$$当 $n\to\infty$ 时选中真正中位数的概率比普通实现提升 $\frac{3}{2}$ 倍好分割$n/3 \le i \le 2n/3$的概率则由 $\frac{1}{3}$ 提升到 $\frac{13}{27}$。这正是 7.4-6 所述三点取中思想的精确化——随机化不改变 $\Theta(n\lg n)$ 的数量级只优化常数因子。7. 在仓库中的位置与进一步阅读本仓库CLRS Solutions以 Markdown KaTeX 组织《算法导论第三版》全书习题解答站点导航定义见 mkdocs.yml其中 7.3 一节位于II Sorting and Order Statistics → 7 Quicksort下。相关资源按阅读顺序推荐7.1 小节快速排序的描述——PARTITION 过程与正确性、$\Theta(n)$ 时间论证7.2 小节快速排序的性能——最坏/最好情况递推、递归树深度与分割概率7.3 小节随机化版本本文核心——期望运行时间的动机与 RANDOM 调用次数7.4 小节快速排序的分析——$\Omega(n^2)$ 下界、$\Omega(n\lg n)$ 上界、插入排序混合优化问题 7-2、问题 7-3、问题 7-5——相等元素、替代分析与 median-of-3。沿这条主线读下来为什么随机化与随机化后如何分析两个问题会形成一个完整的闭环期望分析针对的是算法内部的随机性它无法被输入对抗性构造因此随机化快速排序能够在任意输入上获得 $\Theta(n\lg n)$ 的期望保证而 RANDOM 调用本身仅为 $\Theta(n)$ 次线性开销——这就是第 7.3 节全部习题要传达的核心。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐随机化快速排序的期望性能分析CLRS 7.3 节习题精解与 Python 实现验证随机化快速排序的期望性能分析CLRS 7.3 节习题精解与 Python 实现验证 导读 快速排序Quicksort是算法导论CLRSIntroduc文档教程示例工程CLRS 快速排序深度分析从最坏情况递推到随机化期望时间第 7.4 节习题全解CLRS 快速排序深度分析从最坏情况递推到随机化期望时间第 7.4 节习题全解 导读 本文围绕 CLRS《算法导论》第 7 章第 4 节7.4 Anal文档教程示例工程CLRS 习题解析 7.2快速排序Quicksort性能分析——最坏情况、平衡划分与随机化期望CLRS 习题解析 7.2快速排序Quicksort性能分析——最坏情况、平衡划分与随机化期望 导读 本节聚焦《算法导论》第 7 章 7.2 节快速排文档教程示例工程上一篇7个关键能力nvme-cli如何重塑企业NVMe存储管理下一篇猫抓 cat-catch 完整指南10 分钟上手的免费网页视频下载工具含 M3U8 分片合并创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考