 下界)
文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载导读本文基于本仓库 C08-Sorting-in-Linear-Time/8.1.md 中《算法导论》CLRS第 8 章第 8.1 节的四个习题及其解答系统梳理比较排序下界的决策树论证脉络从叶子最小深度、lg(n!) 的紧渐近界到线性时间比较排序的不可能性、再到分治变体的 Ω(n lg k) 下界。读完本文你将完整掌握任何基于比较的排序算法最坏情况下至少需要 Ω(n lg n) 次比较的证明思路并理解计数、基数、桶排序为何能在特殊输入模型下突破这一下界。1. 背景比较排序为什么存在下界——决策树模型本节的主题CLRS 8.1 Lower bounds for sorting回答一个根本性问题为什么通用排序算法最快也只能做到 Θ(n lg n)。模型前提是比较排序算法唯一允许的操作是两两比较元素的大小a b或a ≤ b除此之外不能利用元素值的任何结构信息。插入排序、归并排序、堆排序、快速排序都属于此类。决策树模型把一次排序执行抽象为一棵二叉树每个内部节点代表一次比较左、右子树分别对应该比较的两种结果是/否每条根到叶子的路径对应输入元素的一个排列比较序列及其结论由于 n 个互异元素共有 n! 种可能排列正确的排序算法必须能区分全部 n! 种输出因此决策树至少有 n! 片叶子对一棵二叉树高度为 h 时叶子数至多 2^h于是$$2^h \ge n! \quad\Rightarrow\quad h \ge \lg(n!) \Theta(n\lg n)$$其中最后一步用到 Stirling 近似 $\lg(n!) \Theta(n\lg n)$。这就是比较排序最坏情况 $\Omega(n\lg n)$ 下界的标准证明。需要特别强调的是该下界只适用于通用比较排序。第 8.28.4 节的计数排序、基数排序、桶排序因为额外利用了输入元素的值域很小 / 均匀分布 / 基数固定等输入模型信息可以做到线性时间这正是仓库中 C08-Sorting-in-Linear-Time/8.2.md、8.3.md、8.4.md 分别讲解的内容。2. 习题 8.1-1决策树叶子节点的最小深度为 n−1题目对于一个比较排序的决策树叶子节点的最小可能深度是多少解答8.1.md 给出的答案当数组已经排好序时最小深度为 n−1。论证分两步下界至少 n−1考察已排序输入对应的叶子。把 n 个元素看作图的顶点每次比较给两个顶点连一条边。算法若确信整个序列有序则任意两个元素之间的相对次序都必须经由比较链条确定即这个比较图必须是连通的——连通图至少需要 n−1 条边因此至少执行 n−1 次比较对应叶子深度 ≥ n−1。若某次比较的图不连通则存在未被比较关系约束的两个元素可以互换位置而不与任何比较结果矛盾排序就不可靠。上界n−1 可达到插入排序处理已排序输入时每个新元素只需与前面紧邻元素比较一次即可就位总共恰好 n−1 次比较。3. 习题 8.1-2不用 Stirling 公式求 lg(n!) 的紧渐近界题目不使用 Stirling 近似改为直接估计求和 $\sum_{k1}^{n}\lg k$利用 CLRS 附录 A.2 的求和技巧积分法、上下界夹逼等给出 lg(n!) 的紧渐近界。解答因为 $\lg(n!) \sum_{k1}^{n}\lg k$只需分别给出上下界。上界每一项都不超过 $\lg n$$$\sum_{k1}^{n}\lg k ;\le; \sum_{k1}^{n}\lg n n\lg n O(n\lg n)$$下界关键配对技巧$n!^2 \prod_{k1}^{n} k\cdot(n1-k)$对任意 $1 \le k \le n$有 $k(n1-k) \ge n$端点 $k1$ 或 $kn$ 时取等号 $n$因此$$n!^2 \prod_{k1}^{n}k(n1-k) \ge n^n \quad\Rightarrow\quad n! \ge n^{n/2} \sqrt{n^{,n}}$$两边取对数即得文档中的关键不等式$$\sum_{k1}^{n}\lg k ;; \lg(n!) ;\ge; \lg\bigl(\sqrt{n^{,n}}\bigr) \frac{n}{2}\lg n \Omega(n\lg n)$$结论上下界结合得到 $\lg(n!) \Theta(n\lg n)$。这条结论正是第 1 节决策树论证 $h \ge \lg(n!) \Theta(n\lg n)$ 的最终落点也是全章下界证明的基石。4. 习题 8.1-3不存在对大量输入线性时间的比较排序题目证明不存在这样的比较排序对长度 n 的 n! 个输入中至少一半的输入其运行时间是线性的。若换成 $1/n$ 比例的输入呢换成 $1/2^n$ 比例呢解答文档答案要点$n!/2$、$n!/n$、$n!/(2^n)$ 这三个量只在 n 很小时小于 $2^n$对足够大的 n它们都远超 $2^n$因此不可能有线性时间的比较排序。完整论证如下若某排序对 m 个输入运行时间线性即至多 $cn$ 次比较c 为常数那么决策树中深度不超过 $cn$ 的叶子至少要有 m 片深度不超过 $cn$ 的叶子至多有 $2^{cn}$ 片二叉树每层叶子数上界而 $2^{cn}$ 与 $2^n$ 同阶于是要求 $m \le 2^{cn}$。分别代入三种比例一半输入$m n!/2$$1/n$ 比例$m n!/n$$1/2^n$ 比例$m n!/2^n$由上一题 $\lg(n!) \Theta(n\lg n)$$n!$ 的渐近增长速度远超 $2^n$上述三个 m 除 n 极小时都大于 $2^{cn}$矛盾。直观理解想让相当比例哪怕是 $1/2^n$的输入在树的上层就收敛到叶子就必须在上层容纳海量叶子而二叉树的容量按 $2^{深度}$ 增长根本追不上 $n!$ 的增长速度。5. 习题 8.1-4子序列分治变体的 Ω(n lg k) 下界题目给定长度为 n 的序列它由 n/k 个子序列组成每个子序列含 k 个元素且第 i 个子序列的所有元素都小于第 i1 个子序列的所有元素。因此只需分别排序这 n/k 个子序列即可完成整体排序。证明该变体所需的比较次数下界为 Ω(n lg k)。题目 Hint 特别提醒简单地把各子序列的 $\Omega(k\lg k)$ 下界相加是不严谨的。解答文档给出如下计数推导统计合法输出的总数每个子序列内部元素可任意排列共 k! 种n/k 个子序列相互独立值域互不重叠跨子序列的顺序已经天然确定因此整个序列的合法排列总数为$$(k!)^{n/k}$$把它代入决策树容量约束 $2^h \ge \text{叶子数}$$$2^h \ge (k!)^{n/k}\quad\Rightarrow\quad h \ge \lg\bigl((k!)^{n/k}\bigr) \frac{n}{k}\cdot\lg(k!)$$再由 8.1-2 的结论 $\lg(k!) \Theta(k\lg k)$得到$$h \Omega!\left(\frac{n}{k}\cdot k\lg k\right) \Omega(n\lg k)$$关于 Hint 的解读朴素思路是每个子序列独立排序需要 $\Omega(k\lg k)$ 次比较n/k 个子序列相加得 $\Omega(n\lg k)$。它不够严谨的原因在于整个问题的决策树是一个整体结构跨子序列的比较会在树上共享节点各子序列的决策树并非互不相交的并集简单相加忽略了这种共享与相互干扰。严谨的做法是像上文那样直接对整体输出空间计数——先数出合法输出的总数 $(k!)^{n/k}$再代入整体决策树的高度约束这样才把输出空间大小决定树高下界这一根本机制用到位。值得一提的是朴素相加恰好得到了相同的结果但只有输出空间计数路径是严格可证的。6. 仓库配套线性时间排序实现与下界的延伸阅读第 8.1 节的下界回答了比较排序能有多快而仓库中同章节的配套源码恰好给出了绕开下界的另一面——利用输入结构信息换取线性时间in_place_counting_sort.py对应 problem.md 中 Problem 8-2e 的原位计数排序实现在 O(n k) 时间内就地排序值域 1k牺牲稳定性换取常数额外空间radixSort.cpp对应 8.3.md 习题 8.3-4 的基数排序实现——把 0 到 n²−1 的整数视为 n 进制数两趟计数排序即得 O(n) 时间intergerQuery.cpp对应 8.2.md 习题 8.2-4 的O(1) 区间计数查询实现——预处理前缀和数组 C区间 [a, b] 的元素个数即为 C[b] − C[a−1]water-jugs.py对应 problem.md Problem 8-4 的水壶配对随机算法实现其随机选基准、递归划分的思想与快速排序同构期望比较次数 O(n lg n)。这些实现的价值在于从反面印证第 8.1 节的核心结论下界成立的前提是仅靠元素间比较。计数排序依赖值域 k、基数排序依赖位数 d、桶排序依赖均匀分布假设一旦这些额外信息可用线性时间排序8.2.md、8.3.md、8.4.md 分别详述便成为可能。此外problem.md 的Problem 8-1把下界从最坏情况推广到平均情况借助外部路径长度 $D(T) D(L_T) D(R_T) k$ 的递推关系证明 $d(k) \Theta(k\lg k)$从而得出任何确定性或随机化比较排序对随机输入的期望运行时间同样是 $\Theta(n\lg n)$——这可以看作第 8.1 节决策树模型的自然延伸。仓库根目录 README.md 的 Data Structure algorithm implementation 一节同样收录了计数排序与基数排序的实现链接可作为继续深入第 8 章其余小节8.2 计数排序、8.3 基数排序、8.4 桶排序的入口。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐CLRS 算法导论 9.1 节习题精解第二小元素与最小/最大值的最优比较次数锦标赛树与成对比较CLRS 算法导论 9.1 节习题精解第二小元素与最小/最大值的最优比较次数锦标赛树与成对比较 本文围绕 C09 Medians and Order St文档教程示例工程CLRS 第 3 章函数增长精解3.1 节 Θ/O/Ω 记号的 8 道经典习题全解析CLRS 第 3 章函数增长精解3.1 节 Θ/O/Ω 记号的 8 道经典习题全解析 本篇技术指南以《算法导论》Introduction to Algori文档教程示例工程CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较 本篇技术指南围绕《算法导论》Introduction to Algorithms,文档教程示例工程上一篇NVIDIA Profile Inspector终极指南解锁200隐藏设置彻底掌控你的显卡性能下一篇OpenReel Video核心引擎全景video、audio、graphics、export四大引擎如何协作创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/5 6:42:40 · 阅读 1.2k CLRS 第 8.1 节习题精解：决策树模型与比较排序的 Ω(n lg n) 下界
文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载导读本文基于本仓库 C08-Sorting-in-Linear-Time/8.1.md 中《算法导论》CLRS第 8 章第 8.1 节的四个习题及其解答系统梳理比较排序下界的决策树论证脉络从叶子最小深度、lg(n!) 的紧渐近界到线性时间比较排序的不可能性、再到分治变体的 Ω(n lg k) 下界。读完本文你将完整掌握任何基于比较的排序算法最坏情况下至少需要 Ω(n lg n) 次比较的证明思路并理解计数、基数、桶排序为何能在特殊输入模型下突破这一下界。1. 背景比较排序为什么存在下界——决策树模型本节的主题CLRS 8.1 Lower bounds for sorting回答一个根本性问题为什么通用排序算法最快也只能做到 Θ(n lg n)。模型前提是比较排序算法唯一允许的操作是两两比较元素的大小a b或a ≤ b除此之外不能利用元素值的任何结构信息。插入排序、归并排序、堆排序、快速排序都属于此类。决策树模型把一次排序执行抽象为一棵二叉树每个内部节点代表一次比较左、右子树分别对应该比较的两种结果是/否每条根到叶子的路径对应输入元素的一个排列比较序列及其结论由于 n 个互异元素共有 n! 种可能排列正确的排序算法必须能区分全部 n! 种输出因此决策树至少有 n! 片叶子对一棵二叉树高度为 h 时叶子数至多 2^h于是$$2^h \ge n! \quad\Rightarrow\quad h \ge \lg(n!) \Theta(n\lg n)$$其中最后一步用到 Stirling 近似 $\lg(n!) \Theta(n\lg n)$。这就是比较排序最坏情况 $\Omega(n\lg n)$ 下界的标准证明。需要特别强调的是该下界只适用于通用比较排序。第 8.28.4 节的计数排序、基数排序、桶排序因为额外利用了输入元素的值域很小 / 均匀分布 / 基数固定等输入模型信息可以做到线性时间这正是仓库中 C08-Sorting-in-Linear-Time/8.2.md、8.3.md、8.4.md 分别讲解的内容。2. 习题 8.1-1决策树叶子节点的最小深度为 n−1题目对于一个比较排序的决策树叶子节点的最小可能深度是多少解答8.1.md 给出的答案当数组已经排好序时最小深度为 n−1。论证分两步下界至少 n−1考察已排序输入对应的叶子。把 n 个元素看作图的顶点每次比较给两个顶点连一条边。算法若确信整个序列有序则任意两个元素之间的相对次序都必须经由比较链条确定即这个比较图必须是连通的——连通图至少需要 n−1 条边因此至少执行 n−1 次比较对应叶子深度 ≥ n−1。若某次比较的图不连通则存在未被比较关系约束的两个元素可以互换位置而不与任何比较结果矛盾排序就不可靠。上界n−1 可达到插入排序处理已排序输入时每个新元素只需与前面紧邻元素比较一次即可就位总共恰好 n−1 次比较。3. 习题 8.1-2不用 Stirling 公式求 lg(n!) 的紧渐近界题目不使用 Stirling 近似改为直接估计求和 $\sum_{k1}^{n}\lg k$利用 CLRS 附录 A.2 的求和技巧积分法、上下界夹逼等给出 lg(n!) 的紧渐近界。解答因为 $\lg(n!) \sum_{k1}^{n}\lg k$只需分别给出上下界。上界每一项都不超过 $\lg n$$$\sum_{k1}^{n}\lg k ;\le; \sum_{k1}^{n}\lg n n\lg n O(n\lg n)$$下界关键配对技巧$n!^2 \prod_{k1}^{n} k\cdot(n1-k)$对任意 $1 \le k \le n$有 $k(n1-k) \ge n$端点 $k1$ 或 $kn$ 时取等号 $n$因此$$n!^2 \prod_{k1}^{n}k(n1-k) \ge n^n \quad\Rightarrow\quad n! \ge n^{n/2} \sqrt{n^{,n}}$$两边取对数即得文档中的关键不等式$$\sum_{k1}^{n}\lg k ;; \lg(n!) ;\ge; \lg\bigl(\sqrt{n^{,n}}\bigr) \frac{n}{2}\lg n \Omega(n\lg n)$$结论上下界结合得到 $\lg(n!) \Theta(n\lg n)$。这条结论正是第 1 节决策树论证 $h \ge \lg(n!) \Theta(n\lg n)$ 的最终落点也是全章下界证明的基石。4. 习题 8.1-3不存在对大量输入线性时间的比较排序题目证明不存在这样的比较排序对长度 n 的 n! 个输入中至少一半的输入其运行时间是线性的。若换成 $1/n$ 比例的输入呢换成 $1/2^n$ 比例呢解答文档答案要点$n!/2$、$n!/n$、$n!/(2^n)$ 这三个量只在 n 很小时小于 $2^n$对足够大的 n它们都远超 $2^n$因此不可能有线性时间的比较排序。完整论证如下若某排序对 m 个输入运行时间线性即至多 $cn$ 次比较c 为常数那么决策树中深度不超过 $cn$ 的叶子至少要有 m 片深度不超过 $cn$ 的叶子至多有 $2^{cn}$ 片二叉树每层叶子数上界而 $2^{cn}$ 与 $2^n$ 同阶于是要求 $m \le 2^{cn}$。分别代入三种比例一半输入$m n!/2$$1/n$ 比例$m n!/n$$1/2^n$ 比例$m n!/2^n$由上一题 $\lg(n!) \Theta(n\lg n)$$n!$ 的渐近增长速度远超 $2^n$上述三个 m 除 n 极小时都大于 $2^{cn}$矛盾。直观理解想让相当比例哪怕是 $1/2^n$的输入在树的上层就收敛到叶子就必须在上层容纳海量叶子而二叉树的容量按 $2^{深度}$ 增长根本追不上 $n!$ 的增长速度。5. 习题 8.1-4子序列分治变体的 Ω(n lg k) 下界题目给定长度为 n 的序列它由 n/k 个子序列组成每个子序列含 k 个元素且第 i 个子序列的所有元素都小于第 i1 个子序列的所有元素。因此只需分别排序这 n/k 个子序列即可完成整体排序。证明该变体所需的比较次数下界为 Ω(n lg k)。题目 Hint 特别提醒简单地把各子序列的 $\Omega(k\lg k)$ 下界相加是不严谨的。解答文档给出如下计数推导统计合法输出的总数每个子序列内部元素可任意排列共 k! 种n/k 个子序列相互独立值域互不重叠跨子序列的顺序已经天然确定因此整个序列的合法排列总数为$$(k!)^{n/k}$$把它代入决策树容量约束 $2^h \ge \text{叶子数}$$$2^h \ge (k!)^{n/k}\quad\Rightarrow\quad h \ge \lg\bigl((k!)^{n/k}\bigr) \frac{n}{k}\cdot\lg(k!)$$再由 8.1-2 的结论 $\lg(k!) \Theta(k\lg k)$得到$$h \Omega!\left(\frac{n}{k}\cdot k\lg k\right) \Omega(n\lg k)$$关于 Hint 的解读朴素思路是每个子序列独立排序需要 $\Omega(k\lg k)$ 次比较n/k 个子序列相加得 $\Omega(n\lg k)$。它不够严谨的原因在于整个问题的决策树是一个整体结构跨子序列的比较会在树上共享节点各子序列的决策树并非互不相交的并集简单相加忽略了这种共享与相互干扰。严谨的做法是像上文那样直接对整体输出空间计数——先数出合法输出的总数 $(k!)^{n/k}$再代入整体决策树的高度约束这样才把输出空间大小决定树高下界这一根本机制用到位。值得一提的是朴素相加恰好得到了相同的结果但只有输出空间计数路径是严格可证的。6. 仓库配套线性时间排序实现与下界的延伸阅读第 8.1 节的下界回答了比较排序能有多快而仓库中同章节的配套源码恰好给出了绕开下界的另一面——利用输入结构信息换取线性时间in_place_counting_sort.py对应 problem.md 中 Problem 8-2e 的原位计数排序实现在 O(n k) 时间内就地排序值域 1k牺牲稳定性换取常数额外空间radixSort.cpp对应 8.3.md 习题 8.3-4 的基数排序实现——把 0 到 n²−1 的整数视为 n 进制数两趟计数排序即得 O(n) 时间intergerQuery.cpp对应 8.2.md 习题 8.2-4 的O(1) 区间计数查询实现——预处理前缀和数组 C区间 [a, b] 的元素个数即为 C[b] − C[a−1]water-jugs.py对应 problem.md Problem 8-4 的水壶配对随机算法实现其随机选基准、递归划分的思想与快速排序同构期望比较次数 O(n lg n)。这些实现的价值在于从反面印证第 8.1 节的核心结论下界成立的前提是仅靠元素间比较。计数排序依赖值域 k、基数排序依赖位数 d、桶排序依赖均匀分布假设一旦这些额外信息可用线性时间排序8.2.md、8.3.md、8.4.md 分别详述便成为可能。此外problem.md 的Problem 8-1把下界从最坏情况推广到平均情况借助外部路径长度 $D(T) D(L_T) D(R_T) k$ 的递推关系证明 $d(k) \Theta(k\lg k)$从而得出任何确定性或随机化比较排序对随机输入的期望运行时间同样是 $\Theta(n\lg n)$——这可以看作第 8.1 节决策树模型的自然延伸。仓库根目录 README.md 的 Data Structure algorithm implementation 一节同样收录了计数排序与基数排序的实现链接可作为继续深入第 8 章其余小节8.2 计数排序、8.3 基数排序、8.4 桶排序的入口。赞分享文档教程示例工程【免费下载链接】CLRS:notebook:Solutions to Introduction to Algorithms项目地址https://gitcode.com/gh_mirrors/cl/CLRS点击查看免费下载相关推荐CLRS 算法导论 9.1 节习题精解第二小元素与最小/最大值的最优比较次数锦标赛树与成对比较CLRS 算法导论 9.1 节习题精解第二小元素与最小/最大值的最优比较次数锦标赛树与成对比较 本文围绕 C09 Medians and Order St文档教程示例工程CLRS 第 3 章函数增长精解3.1 节 Θ/O/Ω 记号的 8 道经典习题全解析CLRS 第 3 章函数增长精解3.1 节 Θ/O/Ω 记号的 8 道经典习题全解析 本篇技术指南以《算法导论》Introduction to Algori文档教程示例工程CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较CLRS 1.2 习题详解应用层算法、插入排序与归并排序的运行时间比较 本篇技术指南围绕《算法导论》Introduction to Algorithms,文档教程示例工程上一篇NVIDIA Profile Inspector终极指南解锁200隐藏设置彻底掌控你的显卡性能下一篇OpenReel Video核心引擎全景video、audio、graphics、export四大引擎如何协作创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考