知识卡片
排序下界依赖比较模型
比较排序仅靠元素间的比较来确定顺序,移动可用交换或复制等方式。对任意互异键都正确的比较排序,最坏比较次数有Ω(n log n)下界;不是说每个输入都至少花这么多时间,也不应把下界写成O上界。
原因是要区分n!种可能次序,固定分支数的比较决策树至少有n!个叶子,最深路径至少log(n!)。利用整数范围、位数等额外结构的计数/基数方法不受同一个纯比较模型约束,但其成本又要计入范围与位数。
原书此段“不可能小于O(n lg n)”按上述条件理解。MIT线性排序讲义,第2页(2026-11-06读取定义/决策树下界)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
比较排序和线性时间排序。比较排序依赖于比较和交换来将元素移动到正确的位置上。令人惊讶的是,并不是所有的排序算法都依赖于比较。对于那些确实依赖于比较来进行排序的算法来说,它们的运行时间往往不可能小于O(nlg n)。对于线性时间排序,从它的名字就可以看出,它的运行时间往往与它处理的数据元素个数成正比,
参考来源
- 位置:《算法精解:C语言描述》第12章《第12章 排序和搜索》(spine1337;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1303_split_001.html;u204-ch12-001)。
- 结论依据:204完整比较/线性排序说明实读,MIT原始讲义核验最坏Ω界与模型前提,不把所有排序算法统一收费。
- 原始内容:比较排序和线性时间排序。比较排序依赖于比较和交换来将元素移动到正确的位置上。令人惊讶的是,并不是所有的排序算法都依赖于比较。对于那些确实依赖于比较来进行排序的算法来说,它们的运行时间往往不可能小于O(nlg n)。对于线性时间排序,从它的名字就可以看出,它的运行时间往往与它处理的数据元素个数成正比,