文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文基于 CLRS《Introduction to Algorithms》第三版题解仓库中第 2 章习题 2-1 的解答docs/Chap02/Problems/2-1.md完整剖析一种混合归并排序的复杂度分析先用插入排序把输入分成 $n/k$ 个长度为 $k$ 的子表并逐个排好再使用标准归并机制把子表合并。读完后你将能够独立完成插入排序阶段 $\Theta(nk)$ 与归并阶段 $\Theta(n\lg(n/k))$ 的证明掌握总量 $\Theta(nk n\lg(n/k))$ 与标准归并排序同阶时 $k$ 的最大取值 $k \Theta(\lg n)$并理解实践中如何确定混合阈值 $k$。上图是混合方案所依赖的基础构件——插入排序INSERTION-SORT在 6 元素数组上的逐步执行示意原图出自 2.1 节练习题。混合归并排序正是把递归分解到这些小叶子为止并改用这种常数因子小的线性/平方级算法来收尾。一、问题背景粗化归并排序的递归叶子标准归并排序的最坏运行时间为 $\Theta(n\lg n)$插入排序的最坏运行时间为 $\Theta(n^2)$。从渐近记号看归并排序完胜但在许多机器上小输入规模下插入排序的常数因子足够小实际运行反而更快——它对几乎有序的输入接近线性访问模式顺序且缓存友好且没有归并所需的额外辅助数组开销。因此一个自然的优化是粗化coarsen归并排序递归树的叶子即当子问题小到足够程度时停止继续二分改用插入排序。原题给出的具体修改方式是将输入划分为 $n/k$ 个长度为 $k$ 的子表其中 $k$ 是待定参数对每个子表用插入排序分别排序用标准归并机制即 2.3 节的MERGE过程把这些有序子表两两归并最终合成一个长度为 $n$ 的有序表。该算法的总运行时间为两部分之和原题分四个小问逐层拆解(a) 插入排序阶段的开销(b) 归并阶段的开销(c) 使总复杂度仍为 $\Theta(n\lg n)$ 的最大 $k$(d) 实践中如何选择 $k$。下面依次给出证明并结合仓库中第 2 章的其他题解补充关键依据。二、第 (a) 问插入排序阶段的开销是 $\Theta(nk)$插入排序的伪代码见 2.1 节2.1-2 题INSERTION-SORT(A) for j 2 to A.length key A[j] i j - 1 while i 0 and A[i] key A[i 1] A[i] i i - 1 A[i 1] key单表分析用插入排序排序一个长度为 $k$ 的表最坏时间为 $\Theta(k^2)$。这一结论在仓库的另一道题解中有更细致的支撑2-4 题 证明了插入排序的运行时间与输入的逆序对inversion数量成正比——while循环每执行一次恰好消除一个逆序对而长度为 $k$ 的表最多有 $k(k-1)/2$ 个逆序对故最坏为 $\Theta(k^2)$。总和分析共有 $n/k$ 个互不重叠的长度为 $k$ 的子表各表相互独立地排序因此$$ \Theta(k^2) \cdot \frac{n}{k} \Theta(nk) $$即插入排序阶段的最坏总时间为 $\Theta(nk)$。注意这里的乘法成立依赖于子表之间无交叉比较——每个元素的移动只发生在其所属子表内部。三、第 (b) 问归并 $n/k$ 个子表需要 $\Theta(n\lg(n/k))$现在假设已有 $n/k$ 个长度为 $k$ 的有序子表要求归并成一个长度为 $n$ 的有序表。归并操作使用的就是 2.3 节的MERGE过程2.3-2 题 给出了不使用哨兵元素的改写版本MERGE(A, p, q, r) n1 q - p 1 n2 r - q let L[1..n1] and R[1..n2] be new arrays for i 1 to n1 L[i] A[p i - 1] for j 1 to n2 R[j] A[q j] i 1 j 1 for k p to r if i n1 A[k] R[j] j j 1 else if j n2 A[k] L[i] i i 1 else if L[i] ≤ R[j] A[k] L[i] i i 1 else A[k] R[j] j j 1一次MERGE扫描参与归并的每个元素常数次比较加回写所以合并总长为 $m$ 的两个有序表是 $\Theta(m)$合并 $m$ 个单元素表为 $m$ 个元素的有序表则是 $\Theta(m\lg m)$。归并树分析原解答的推理方式两两归并的过程可以可视化为一棵归并树——每一轮归并都把子表数量减半、子表长度翻倍$n/k$ 个长度 $k$ 的表 $\to$ $n/(2k)$ 个长度 $2k$ 的表 $\to \cdots$ $\to$ 1 个长度 $n$ 的表轮数树的高度为 $\lg(n/k)$每一层参与归并的元素总数恰好都是 $n$故每层代价 $\Theta(n)$。因此归并阶段的最坏总时间为$$ \Theta(n) \cdot \lg(n/k) \Theta(n\lg(n/k)) $$这一每层 $\Theta(n)$、共 $\lg(n/k)$ 层的论证与标准归并排序递推式 $T(n) 2T(n/2) n$ 的解法完全同构参见 2.3 节 2.3-3 题 中对该递推式的数学归纳证明$n$ 为 2 的幂时 $T(n) n\lg n$。若 $n/k$ 不是 2 的整数次幂层数取 $\lceil \lg(n/k) \rceil$在 $\Theta$ 记号下结论不变。四、第 (c) 问使总时间与标准归并排序同阶的最大 $k$综合前两问混合算法的最坏运行时间为$$ T(n) \Theta(nk n\lg(n/k)) $$要求它仍等于 $\Theta(n\lg n)$标准归并排序的量级。原解答取 $k \Theta(\lg n)$ 代入验证$$ \begin{aligned} \Theta(nk n\lg(n / k)) \Theta(n\lg n n\lg n - n\lg(\lg n)) \ \Theta(2n\lg n - n\lg(\lg n)) \ \Theta(n\lg n). \end{aligned} $$其中用到了 $\lg(n/k) \lg n - \lg k$ 与 $\lg(\lg n) o(\lg n)$$2n\lg n - n\lg(\lg n)$ 与 $n\lg n$ 相差不到一个常数倍故总量仍为 $\Theta(n\lg n)$。为什么 $k \Theta(\lg n)$ 是最大值$k$ 取更大的值时第一项 $nk$ 会压过 $n\lg n$ 项。例如取 $k (\lg n)^2$则 $nk n(\lg n)^2 \omega(n\lg n)$总量变为 $\Theta(n(\lg n)^2)$已超出标准归并排序的量级。反过来$k$ 再小一些例如任意 $k \le c\lg n$ 的常数倍时$nk O(n\lg n)$ 且 $n\lg(n/k) \Theta(n\lg n)$总量仍是 $\Theta(n\lg n)$。因此在 $\Theta$ 记号意义下最大的 $k$ 是 $k \Theta(\lg n)$——超过它渐近复杂度就退化小于它则归并项主导总量恰好是标准归并排序的 $\Theta(n\lg n)$。五、第 (d) 问实践中如何选择 $k$原解答给出的原则是把 $k$ 选为插入排序比归并排序更快的最大子表长度。这句话值得展开为可操作的工程方法$k$ 是机器相关的常数不需要跟随 $n$ 增长。理论上限 $k \Theta(\lg n)$ 只保证不劣化渐近复杂度而渐近分析中的常数因子插入排序的比较/移动代价 vs 归并的辅助数组拷贝代价恰恰在小规模上占主导所以真实最优点几乎总是某个固定的小常数。用基准测试确定。在目标平台、目标数据类型整数、浮点、结构体、缓存行为上对 $k$ 取不同常数实测混合排序与纯归并排序的运行时间取交叉点附近。这也是原解答以实测为准原则的直接推论。结合输入特征微调。由 2-4 题 的结论插入排序耗时正比于子表逆序对数若实际数据接近有序插入排序在子表上接近 $\Theta(n)$$k$ 可以适当放大若数据接近逆序插入排序在子表上逼近 $\Theta(k^2)$$k$ 应取小。不要寄望于聪明的搜索来改变插入排序的复杂度类。2.3-6 题 已经说明即使把while循环中的线性扫描换成二分查找$\Theta(\lg j)$被大于key的元素整体右移的开销仍是 $\Theta(j)$插入排序的最坏时间依然是 $\Theta(n^2)$。也就是说混合方案里插入排序的收益来自常数因子与内存局部性而非复杂度类变化——这决定了 $k$ 必须保持较小。从源码结构看这一阈值切换模式在工程实现中非常普遍许多生产级排序库都会在递归排序中设置一个小的子序列阈值低于阈值改用插入排序。CLRS 仓库本身是算法题解站使用 MkDocs KaTeX 静态站点生成配置见 mkdocs.yml并没有排序器的可执行实现因此上述第 2、3 点应理解为对真实排序库的移植建议而不是对本仓库某段代码的引用。六、结果汇总阶段 / 问题复杂度结论关键推理(a) $n/k$ 个长度为 $k$ 的子表各用插入排序$\Theta(nk)$ 最坏单表 $\Theta(k^2)$表数 $n/k$(b) 用标准MERGE合并这些子表$\Theta(n\lg(n/k))$ 最坏归并树每层 $\Theta(n)$共 $\lg(n/k)$ 层混合算法总量$\Theta(nk n\lg(n/k))$两阶段相加(c) 与 $\Theta(n\lg n)$ 同阶的最大 $k$$k \Theta(\lg n)$更大的 $k$ 使 $nk \omega(n\lg n)$(d) 实践选择实测确定的小常数插入排序占优的最大子表长度七、延伸阅读围绕这道题涉及的构件仓库第 2 章还有几篇直接相关的题解值得对照阅读2.1 插入排序INSERTION-SORT伪代码、逆序/循环不变式证明、线性查找2.3 算法设计归并排序执行过程示意、无哨兵的MERGE改写、递推式 $T(n) 2T(n/2) n$ 的归纳证明、递归插入排序的递推式2.3-4 题以及二分查找为何救不了插入排序最坏情形2.3-6 题2-4 逆序对另一个修改归并排序的经典范例——在MERGE中累计跨半区逆序对以 $\Theta(n\lg n)$ 时间统计逆序对数量其COUNT-INVERSIONS/MERGE-INVERSIONS伪代码展示了修改MERGE时的常见写法带哨兵的数组构造方式可与本文 (b) 问的归并树分析互为印证。掌握本题后你就具备了阅读任何归并排序 小表阈值混合实现以及 2-4 题这类归并变体的复杂度分析能力先分别估计阈值以下的小规模排序代价与阈值以上的归并树代价再比较两者与 $n\lg n$ 的量级关系。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第2章 Problems 全解析混合归并排序、冒泡排序正确性、Horner 规则与逆序对统计CLRS 第2章 Problems 全解析混合归并排序、冒泡排序正确性、Horner 规则与逆序对统计 本文是《算法导论》CLRS第2章Getting文档教程示例工程CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较 本篇技术指南围绕《算法导论》Introduction to Algorithms,文档教程示例工程codeforces-go中的排序归并排序实现codeforces go中的排序归并排序实现 在算法竞赛中排序算法是解决许多问题的基础工具。归并排序Merge Sort作为一种高效的排序算法以其稳科学计算上一篇docker-mailserver 用户补丁机制全解析用 user-patches.sh 定制容器内任意配置与行为下一篇Prettier Markdown 引用链接格式化机制从 CJK 长标签测试看换行决策与源码实现创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载本文基于 CLRS《Introduction to Algorithms》第三版题解仓库中第 2 章习题 2-1 的解答docs/Chap02/Problems/2-1.md完整剖析一种混合归并排序的复杂度分析先用插入排序把输入分成 $n/k$ 个长度为 $k$ 的子表并逐个排好再使用标准归并机制把子表合并。读完后你将能够独立完成插入排序阶段 $\Theta(nk)$ 与归并阶段 $\Theta(n\lg(n/k))$ 的证明掌握总量 $\Theta(nk n\lg(n/k))$ 与标准归并排序同阶时 $k$ 的最大取值 $k \Theta(\lg n)$并理解实践中如何确定混合阈值 $k$。上图是混合方案所依赖的基础构件——插入排序INSERTION-SORT在 6 元素数组上的逐步执行示意原图出自 2.1 节练习题。混合归并排序正是把递归分解到这些小叶子为止并改用这种常数因子小的线性/平方级算法来收尾。一、问题背景粗化归并排序的递归叶子标准归并排序的最坏运行时间为 $\Theta(n\lg n)$插入排序的最坏运行时间为 $\Theta(n^2)$。从渐近记号看归并排序完胜但在许多机器上小输入规模下插入排序的常数因子足够小实际运行反而更快——它对几乎有序的输入接近线性访问模式顺序且缓存友好且没有归并所需的额外辅助数组开销。因此一个自然的优化是粗化coarsen归并排序递归树的叶子即当子问题小到足够程度时停止继续二分改用插入排序。原题给出的具体修改方式是将输入划分为 $n/k$ 个长度为 $k$ 的子表其中 $k$ 是待定参数对每个子表用插入排序分别排序用标准归并机制即 2.3 节的MERGE过程把这些有序子表两两归并最终合成一个长度为 $n$ 的有序表。该算法的总运行时间为两部分之和原题分四个小问逐层拆解(a) 插入排序阶段的开销(b) 归并阶段的开销(c) 使总复杂度仍为 $\Theta(n\lg n)$ 的最大 $k$(d) 实践中如何选择 $k$。下面依次给出证明并结合仓库中第 2 章的其他题解补充关键依据。二、第 (a) 问插入排序阶段的开销是 $\Theta(nk)$插入排序的伪代码见 2.1 节2.1-2 题INSERTION-SORT(A) for j 2 to A.length key A[j] i j - 1 while i 0 and A[i] key A[i 1] A[i] i i - 1 A[i 1] key单表分析用插入排序排序一个长度为 $k$ 的表最坏时间为 $\Theta(k^2)$。这一结论在仓库的另一道题解中有更细致的支撑2-4 题 证明了插入排序的运行时间与输入的逆序对inversion数量成正比——while循环每执行一次恰好消除一个逆序对而长度为 $k$ 的表最多有 $k(k-1)/2$ 个逆序对故最坏为 $\Theta(k^2)$。总和分析共有 $n/k$ 个互不重叠的长度为 $k$ 的子表各表相互独立地排序因此$$ \Theta(k^2) \cdot \frac{n}{k} \Theta(nk) $$即插入排序阶段的最坏总时间为 $\Theta(nk)$。注意这里的乘法成立依赖于子表之间无交叉比较——每个元素的移动只发生在其所属子表内部。三、第 (b) 问归并 $n/k$ 个子表需要 $\Theta(n\lg(n/k))$现在假设已有 $n/k$ 个长度为 $k$ 的有序子表要求归并成一个长度为 $n$ 的有序表。归并操作使用的就是 2.3 节的MERGE过程2.3-2 题 给出了不使用哨兵元素的改写版本MERGE(A, p, q, r) n1 q - p 1 n2 r - q let L[1..n1] and R[1..n2] be new arrays for i 1 to n1 L[i] A[p i - 1] for j 1 to n2 R[j] A[q j] i 1 j 1 for k p to r if i n1 A[k] R[j] j j 1 else if j n2 A[k] L[i] i i 1 else if L[i] ≤ R[j] A[k] L[i] i i 1 else A[k] R[j] j j 1一次MERGE扫描参与归并的每个元素常数次比较加回写所以合并总长为 $m$ 的两个有序表是 $\Theta(m)$合并 $m$ 个单元素表为 $m$ 个元素的有序表则是 $\Theta(m\lg m)$。归并树分析原解答的推理方式两两归并的过程可以可视化为一棵归并树——每一轮归并都把子表数量减半、子表长度翻倍$n/k$ 个长度 $k$ 的表 $\to$ $n/(2k)$ 个长度 $2k$ 的表 $\to \cdots$ $\to$ 1 个长度 $n$ 的表轮数树的高度为 $\lg(n/k)$每一层参与归并的元素总数恰好都是 $n$故每层代价 $\Theta(n)$。因此归并阶段的最坏总时间为$$ \Theta(n) \cdot \lg(n/k) \Theta(n\lg(n/k)) $$这一每层 $\Theta(n)$、共 $\lg(n/k)$ 层的论证与标准归并排序递推式 $T(n) 2T(n/2) n$ 的解法完全同构参见 2.3 节 2.3-3 题 中对该递推式的数学归纳证明$n$ 为 2 的幂时 $T(n) n\lg n$。若 $n/k$ 不是 2 的整数次幂层数取 $\lceil \lg(n/k) \rceil$在 $\Theta$ 记号下结论不变。四、第 (c) 问使总时间与标准归并排序同阶的最大 $k$综合前两问混合算法的最坏运行时间为$$ T(n) \Theta(nk n\lg(n/k)) $$要求它仍等于 $\Theta(n\lg n)$标准归并排序的量级。原解答取 $k \Theta(\lg n)$ 代入验证$$ \begin{aligned} \Theta(nk n\lg(n / k)) \Theta(n\lg n n\lg n - n\lg(\lg n)) \ \Theta(2n\lg n - n\lg(\lg n)) \ \Theta(n\lg n). \end{aligned} $$其中用到了 $\lg(n/k) \lg n - \lg k$ 与 $\lg(\lg n) o(\lg n)$$2n\lg n - n\lg(\lg n)$ 与 $n\lg n$ 相差不到一个常数倍故总量仍为 $\Theta(n\lg n)$。为什么 $k \Theta(\lg n)$ 是最大值$k$ 取更大的值时第一项 $nk$ 会压过 $n\lg n$ 项。例如取 $k (\lg n)^2$则 $nk n(\lg n)^2 \omega(n\lg n)$总量变为 $\Theta(n(\lg n)^2)$已超出标准归并排序的量级。反过来$k$ 再小一些例如任意 $k \le c\lg n$ 的常数倍时$nk O(n\lg n)$ 且 $n\lg(n/k) \Theta(n\lg n)$总量仍是 $\Theta(n\lg n)$。因此在 $\Theta$ 记号意义下最大的 $k$ 是 $k \Theta(\lg n)$——超过它渐近复杂度就退化小于它则归并项主导总量恰好是标准归并排序的 $\Theta(n\lg n)$。五、第 (d) 问实践中如何选择 $k$原解答给出的原则是把 $k$ 选为插入排序比归并排序更快的最大子表长度。这句话值得展开为可操作的工程方法$k$ 是机器相关的常数不需要跟随 $n$ 增长。理论上限 $k \Theta(\lg n)$ 只保证不劣化渐近复杂度而渐近分析中的常数因子插入排序的比较/移动代价 vs 归并的辅助数组拷贝代价恰恰在小规模上占主导所以真实最优点几乎总是某个固定的小常数。用基准测试确定。在目标平台、目标数据类型整数、浮点、结构体、缓存行为上对 $k$ 取不同常数实测混合排序与纯归并排序的运行时间取交叉点附近。这也是原解答以实测为准原则的直接推论。结合输入特征微调。由 2-4 题 的结论插入排序耗时正比于子表逆序对数若实际数据接近有序插入排序在子表上接近 $\Theta(n)$$k$ 可以适当放大若数据接近逆序插入排序在子表上逼近 $\Theta(k^2)$$k$ 应取小。不要寄望于聪明的搜索来改变插入排序的复杂度类。2.3-6 题 已经说明即使把while循环中的线性扫描换成二分查找$\Theta(\lg j)$被大于key的元素整体右移的开销仍是 $\Theta(j)$插入排序的最坏时间依然是 $\Theta(n^2)$。也就是说混合方案里插入排序的收益来自常数因子与内存局部性而非复杂度类变化——这决定了 $k$ 必须保持较小。从源码结构看这一阈值切换模式在工程实现中非常普遍许多生产级排序库都会在递归排序中设置一个小的子序列阈值低于阈值改用插入排序。CLRS 仓库本身是算法题解站使用 MkDocs KaTeX 静态站点生成配置见 mkdocs.yml并没有排序器的可执行实现因此上述第 2、3 点应理解为对真实排序库的移植建议而不是对本仓库某段代码的引用。六、结果汇总阶段 / 问题复杂度结论关键推理(a) $n/k$ 个长度为 $k$ 的子表各用插入排序$\Theta(nk)$ 最坏单表 $\Theta(k^2)$表数 $n/k$(b) 用标准MERGE合并这些子表$\Theta(n\lg(n/k))$ 最坏归并树每层 $\Theta(n)$共 $\lg(n/k)$ 层混合算法总量$\Theta(nk n\lg(n/k))$两阶段相加(c) 与 $\Theta(n\lg n)$ 同阶的最大 $k$$k \Theta(\lg n)$更大的 $k$ 使 $nk \omega(n\lg n)$(d) 实践选择实测确定的小常数插入排序占优的最大子表长度七、延伸阅读围绕这道题涉及的构件仓库第 2 章还有几篇直接相关的题解值得对照阅读2.1 插入排序INSERTION-SORT伪代码、逆序/循环不变式证明、线性查找2.3 算法设计归并排序执行过程示意、无哨兵的MERGE改写、递推式 $T(n) 2T(n/2) n$ 的归纳证明、递归插入排序的递推式2.3-4 题以及二分查找为何救不了插入排序最坏情形2.3-6 题2-4 逆序对另一个修改归并排序的经典范例——在MERGE中累计跨半区逆序对以 $\Theta(n\lg n)$ 时间统计逆序对数量其COUNT-INVERSIONS/MERGE-INVERSIONS伪代码展示了修改MERGE时的常见写法带哨兵的数组构造方式可与本文 (b) 问的归并树分析互为印证。掌握本题后你就具备了阅读任何归并排序 小表阈值混合实现以及 2-4 题这类归并变体的复杂度分析能力先分别估计阈值以下的小规模排序代价与阈值以上的归并树代价再比较两者与 $n\lg n$ 的量级关系。赞分享文档教程教育【免费下载链接】CLRS Solutions to Introduction to Algorithms Third Edition项目地址https://gitcode.com/gh_mirrors/clr/CLRS点击查看免费下载相关推荐CLRS 第2章 Problems 全解析混合归并排序、冒泡排序正确性、Horner 规则与逆序对统计CLRS 第2章 Problems 全解析混合归并排序、冒泡排序正确性、Horner 规则与逆序对统计 本文是《算法导论》CLRS第2章Getting文档教程示例工程CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较 本篇技术指南围绕《算法导论》Introduction to Algorithms,文档教程示例工程codeforces-go中的排序归并排序实现codeforces go中的排序归并排序实现 在算法竞赛中排序算法是解决许多问题的基础工具。归并排序Merge Sort作为一种高效的排序算法以其稳科学计算上一篇docker-mailserver 用户补丁机制全解析用 user-patches.sh 定制容器内任意配置与行为下一篇Prettier Markdown 引用链接格式化机制从 CJK 长标签测试看换行决策与源码实现创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
