文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本篇基于 CLRSIntroduction to Algorithms, Third Edition题解仓库中的 Exercise 9-1完整分析“给定 n 个数字用基于比较的算法找出最大的 i 个并以排序顺序输出”这一经典 Top-i 选择问题的三种算法路线整体排序、最大优先队列抽取、基于顺序统计量的分区加局部排序。读完后你将掌握每种方法最优渐近最坏运行时间的推导过程$O(n\lg n i)$、$O(n i\lg n)$、$O(n i\lg i)$、它们各自成立的适用场景以及结合第 6 章堆与第 9 章选择算法的完整伪代码实现依据。问题陈述原题引自 docs/Chap09/Problems/9-1.md要求给定一组 $n$ 个数字希望用基于比较的算法找出最大的 $i$ 个并以排序顺序输出。对下列每种方法找出能实现该方法的、渐近最坏运行时间最优的算法并用 $n$ 和 $i$ 分析各算法的运行时间a.对数字排序然后列出最大的 $i$ 个。b.用这些数字构建一个最大优先队列max-priority queue并调用 $\text{EXTRACT-MAX}$ $i$ 次。c.用顺序统计量order-statistic算法找出第 $i$ 大的数围绕该数做分区partition然后对最大的 $i$ 个数排序。问题的两个关键约束值得先说清楚“基于比较”comparison-based意味着不能假设键值域有限不能像计数排序那样绕开比较模型。由 第 8 章练习 8.1-3 的决策树论证可知任何比较排序的最坏情形下界都是 $\Omega(n\lg n)$这是后面评估方法 a 上限是否“浪费”的基准。“以排序顺序”in sorted order意味着输出本身必须是有序的。这一要求决定了方法 b 天然占优堆按序弹出也决定了方法 c 不能止步于“找出前 i 大的集合”还必须在最后补一个规模为 $i$ 的排序。下面逐一给出三种方法的最优实现与运行时间推导。方法 a整体排序后列出前 i 个 —— $O(n\lg n i)$算法TOP-I-BY-SORT(A, n, i) MERGE-SORT(A) // 任何比较排序如 MERGE-SORT / HEAPSORT / QUICKSORT return A[n - i 1 .. n] // 升序排列下最大的 i 个输出代价 O(i)运行时间推导排序阶段任意基于比较的排序算法的最优渐近最坏运行时间为 $\Theta(n\lg n)$上界来自归并排序、堆排序等实现下界来自比较排序决策树的 $\lg(n!) \Theta(n\lg n)$见 docs/Chap08/8.1.md 的 8.1-2、8.1-3 练习。列出阶段排序完成后最大的 $i$ 个数就位于数组末尾连续 $i$ 个位置把它们顺序输出只需 $O(i)$。因此总运行时间为$$T_a(n, i) O(n\lg n i).$$由于 $i \le n$上式实际上就是 $\Theta(n\lg n)$ 量级——排序的代价完全由 $n$ 决定与 $i$ 几乎无关。当 $i$ 远小于 $n$例如只要最大 10 个时这是明显的浪费为了取 $i$ 个元素付出了对全部 $n$ 个元素排序的代价。方法 a 的优势只在 $i \Theta(n)$ 时才体现出来。方法 b构建最大优先队列并抽取 i 次 —— $O(n i\lg n)$算法TOP-I-BY-HEAP(A, n, i) BUILD-MAX-HEAP(A) // 自底向上建堆O(n) for j 1 to i E[j] MAX-HEAP-EXTRACT(A) // 每次 O(lg n) return E // E[1] E[2] ... E[i]天然有序其中一次 $\text{EXTRACT-MAX}$ 的过程对应 CLRS 6.5 节的 $\text{MAX-HEAP-EXTRACT}$ 过程本仓库 docs/Chap06/6.5.md 的 6.5-3 给出了同构的最小堆版本 $\text{HEAP-EXTRACT-MIN}$ 伪代码逻辑完全对称可作为实现参考MAX-HEAP-EXTRACT(A) if A.heap-size 1 error heap underflow max A[1] // 堆顶即当前最大值 A[1] A[A.heap-size] // 用最后一个元素补位 A.heap-size A.heap-size - 1 MAX-HEAPIFY(A, 1) // 自根向下调整O(lg n) return max运行时间推导三个代价项在仓库其他题解中都有直接佐证建堆 $O(n)$$\text{BUILD-MAX-HEAP}$ 从 $\lfloor n/2 \rfloor$ 号节点向下依次调用 $\text{MAX-HEAPIFY}$。之所以必须自底向上下标递减是因为 $\text{MAX-HEAPIFY}(A, i)$ 的前提是 $A$ 的子树已是堆见 docs/Chap06/6.3.md 的 6.3-2而整个建堆过程通过按节点高度分层估计 $\text{MAX-HEAPIFY}$ 的调用代价可加出 $\Theta(n)$而非 $n$ 次 $\Theta(\lg n)$ 的朴素 $O(n\lg n)$。每次抽取 $O(\lg n)$抽取后根节点被替换为末尾元素$\text{MAX-HEAPIFY}$ 沿一条从根到叶的路径下沉路径长度不超过堆高 $\lfloor \lg n \rfloor$故为 $O(\lg n)$其最坏情形确实是 $\Omega(\lg n)$见 docs/Chap06/6.2.md 的 6.2-6。第 $j$ 次抽取时堆规模已经降到 $n-j1$但 $\lg(n-j1) \le \lg n$每次抽取仍按 $O(\lg n)$ 计即可。输出顺序免费获得每次弹出的都是“当前剩余元素中的最大值”所以序列 $E[1], E[2], \dots, E[i]$ 自动满足 $E[1] \ge E[2] \ge \cdots \ge E[i]$恰好就是题目要求的“排序顺序”不需要任何额外排序步骤。因此总运行时间为$$T_b(n, i) O(n i\lg n).$$实现细节提示若用“弹出后不再放回”的方式抽取堆规模单调缩小A.heap-size的维护就是上面伪代码第 4 行若中途需要删除堆中任意指定位置例如把已弹出元素与堆内元素交换要注意简单的“补位 $\text{MAX-HEAPIFY}$”并不总是正确的——docs/Chap06/6.5.md 的 6.5-8 用反例 $\langle 15, 7, 9, 1, 2, 3, 8 \rangle$ 展示了必须根据替换值与被删值的大小关系决定向下 $\text{MAX-HEAPIFY}$ 还是向上升的 $\text{HEAP-DELETE}$ 写法这一细节在方法 b 的变体实现中同样适用。方法 c顺序统计量定位第 i 大分区后只排前 i 个 —— $O(n i\lg i)$这是三种方法中渐近最优的路线核心思想是只让昂贵的“对数排序”作用在真正需要输出的 $i$ 个元素上而对 $n$ 只付出一次线性扫描的代价。算法TOP-I-BY-SELECT(A, n, i) // 第 i 大 第 (n - i 1) 小 q SELECT(A, 1, n, n - i 1) // 最坏 O(n)或用 RANDOMIZED-SELECT期望 O(n) // 此时 A[1..q-1] 全部 A[q]A[q1..n] 全部 A[q] // 最大的 i 个 { A[q] } ∪ A[q1..n]共 1 (n - q) i 个 B [ A[q] ] plus A[q1 .. n] SORT(B) // 只排 i 个元素O(i lg i) return B正确性依赖 $\text{SELECT}$ 内部 $\text{PARTITION}$ 的不变式分区后枢轴落在正确位置 $q$左侧全部小于枢轴、右侧全部大于枢轴$\text{PARTITION}$ 的行为可对照 docs/Chap07/7.1.md 的 7.1-1 逐步示例验证。由于枢轴是第 $(n-i1)$ 小也就是第 $i$ 大它右侧恰好有 $n - q i - 1$ 个比它大的元素把枢轴本身算上正好是“最大的 $i$ 个”无需再做任何筛选。运行时间推导找第 $i$ 大并分区 $O(n)$$\text{SELECT}$中位数的中位数算法保证最坏情形线性时间见 docs/Chap09/9.3.md$\text{RANDOMIZED-SELECT}$ 期望线性时间其迭代式伪代码可在 docs/Chap09/9.2.md 的 9.2-3 中直接复用while 循环逐层收缩 $p, r$每次只保留一侧递归单趟扫描无重复遍历。注意“第 $i$ 大”是降序视角调用时换算成升序的第 $(n-i1)$ 小即可。排序最大的 $i$ 个 $O(i\lg i)$此时只剩一个规模为 $i$ 的排序子问题比较排序的下界 $\Omega(i\lg i)$ 恰好也是它的上界。因此总运行时间为$$T_c(n, i) O(n i\lg i).$$与方法 b 的逐项对比两种方法都先付 $O(n)$ 的“线性前置代价”差别只在抽取阶段的对数项项方法 b方法 c前置结构建立建最大堆$O(n)$$\text{SELECT}$ 分区$O(n)$获取 i 个最大元素$i$ 次 $\text{EXTRACT-MAX}$每次 $O(\lg n)$分区结果直接给出$O(1)$除枢轴外元素已在 $A[q1..n]$输出排序弹出顺序天然有序需对 $i$ 个元素补排序$O(i\lg i)$总计$O(n i\lg n)$$O(n i\lg i)$由于 $i \le n$恒有 $i\lg i \le i\lg n$方法 c 的渐近代价从不劣于方法 b且当 $i \ll n$ 时严格更优例如 $i$ 为常数时方法 c 是 $O(n)$方法 b 是 $O(n \lg n)$ 同阶但常数路径不同更典型的差距出现在 $i \sqrt{n}$ 这类中间量级$i\lg i \Theta(\sqrt{n})$ 而 $i\lg n \Theta(\sqrt{n}\lg n)$。唯一的“打平”发生在 $i n$两者都退化为对全数组的 $\Theta(n\lg n)$ 排序。三种方法的总结与选型方法最优渐近最坏运行时间主导代价适用场景a. 排序后截取$O(n\lg n i)$对 $n$ 个元素全排序$i \Theta(n)$或需要完整有序序列b. 最大优先队列抽 $i$ 次$O(n i\lg n)$$i$ 次堆顶抽取$i$ 中等、且希望“边抽边用”的在线输出c. 顺序统计量 局部排序$O(n i\lg i)$$\text{SELECT}$ 线性分区 对 $i$ 个元素排序$i \ll n$ 的通用最优选择几点结论性分析$O(n)$ 项已是比较模型下的必要代价。仅找最大值就需要 $n-1$ 次比较docs/Chap09/9.1.md 的 9.1-1 用锦标赛法证明了 $n \lceil \lg n \rceil - 2$ 次比较可找次小值其前提正是找最小值本身要 $n-1$ 次比较。任何算法连“读”出最大的 $i$ 个元素都不可能少于 $\Omega(n)$ 次比较所以方法 b、c 中的线性项已经是最优量级。$i n$ 时三者殊途同归。输出整个有序序列就是排序问题本身受 $\Omega(n\lg n)$ 决策树下界约束三种方法全部达到 $\Theta(n\lg n)$谁都不浪费。方法 c 是本题三个方案中渐近上最好的它在 $i$ 从常数到 $n$ 的全区间内都不劣于方法 b并在 $i \ll n$ 时给出 $O(n i\lg i)$ 的紧界。工程实现时若不想手写 $\text{SELECT}$用期望线性的 $\text{RANDOMIZED-SELECT}$docs/Chap09/9.2.md 中的迭代版本替代也是常见做法此时第 1 步变为期望 $O(n)$ 而非最坏 $O(n)$。方法 b 的独特价值在于在线性。它的输出是流式的——第 $j$ 次 $\text{EXTRACT-MAX}$ 返回后立即就拿到第 $j$ 大元素适合“边产出边消费”的场景方法 c 则必须先完成一次 $O(n)$ 的 $\text{SELECT}$ 才能开始输出属于批处理风格。相关仓库文档本题原题与官方题解docs/Chap09/Problems/9-1.md最小/最大值的比较次数分析支撑 $O(n)$ 下界论证docs/Chap09/9.1.md$\text{RANDOMIZED-SELECT}$ 期望线性时间与迭代式伪代码docs/Chap09/9.2.md$\text{SELECT}$ 最坏线性时间与中位数的中位数算法docs/Chap09/9.3.md$\text{MAX-HEAPIFY}$ 运行时间与迭代实现docs/Chap06/6.2.md$\text{BUILD-MAX-HEAP}$ 为何自底向上、$\Theta(n)$ 建堆docs/Chap06/6.3.md优先队列接口与 $\text{HEAP-EXTRACT-MIN}$、$\text{HEAP-DELETE}$ 伪代码docs/Chap06/6.5.md$\text{PARTITION}$ 逐步示例与方法论docs/Chap07/7.1.md比较排序决策树下界docs/Chap08/8.1.md赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较 本篇技术指南围绕《算法导论》Introduction to Algorithms,文档教程示例工程智能字体重塑告别游戏乱码焕新多语言显示体验智能字体重塑告别游戏乱码焕新多语言显示体验 还在为游戏中的方块字烦恼吗Warcraft Font MergerWFM为您带来革命性的字体合并解决方案开发工具游戏开发CLRS 第一章 Problem 1-1 深度解析运行时间比较表与最大可解问题规模的计算方法CLRS 第一章 Problem 1 1 深度解析运行时间比较表与最大可解问题规模的计算方法 本文围绕《算法导论》Introduction to Algor文档教程示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考