知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a · 生成模型:未记录

排序下界依赖比较模型

理解等级:中级

比较排序仅靠元素间的比较来确定顺序,移动可用交换或复制等方式。对任意互异键都正确的比较排序,最坏比较次数有Ω(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)。对于线性时间排序,从它的名字就可以看出,它的运行时间往往与它处理的数据元素个数成正比,