数据结构与算法 / 系统课时

比较排序下界

比较排序下界

归并排序与快速排序的执行过程不同,但都可通过比较取得排序信息。本课用决策树解释为什么比较模型中的算法最坏至少要进行 Ω(nlog⁡n)\Omega(n\log n) 次比较。

学习目标

  • 理解比较决策树的节点、分支与输出映射。
  • 从互异元素的 n!n! 个次序推导最坏比较次数。
  • 区分信息论下界、实际比较次数和利用键值结构的排序。

一条路径只能决定一种位置次序

固定输入长度 nn,考虑互异键。算法只允许通过比较了解键的次序,因此一次有效比较只有“小于”和“大于”两种结果。一个确定性算法可展开成决策树:内部节点选择要比较的两个记录,边表示结果,叶子确定原始位置的输出排列。不同的相对次序要求不同的输出位置排列。若同一叶子包含两种不同次序,就至少有一种不能得到正确输出。 MIT 比较排序下界课程资料

比较排序决策树下界示意

互异键共有 n!n! 种相对次序,所以树至少要有 n!n! 个可达叶子。最大深度为 hh 的二叉树最多有 2h2^h 个叶子,因此 h≥⌈log⁡2(n!)⌉h≥\lceil\log_2(n!)\rceil。这给出最坏比较次数的必要下界。上界可用 n!≤nnn!≤n^n,下界可用阶乘中至少 ⌊n/2⌋\lfloor n/2\rfloor 个因子都不小于 n/2n/2。取对数得 log⁡2(n!)=Θ(nlog⁡n)\log_2(n!)=\Theta(n\log n)。归并排序等算法达到相同量级的最坏比较上界,因此渐进阶紧确。 MIT 比较排序与决策树

用整数位长计算精确下界

对正整数 MM,能容纳至少 MM 个叶子的最小高度是 ⌈log⁡2M⌉\lceil\log_2 M\rceil。用 (M-1).bit_length() 可精确计算,避免浮点对数恰好靠近整数时的舍入。空序列或单元素只有一种位置次序,下界为 0。下面是小规模数值示例,并不搜索可实现的最优比较树。 Python int.bit_length

python
from math import factorial


def comparison_lower_bound(n: int) -> int:
    if type(n) is not int or n < 0:
        raise ValueError("n must be a non-negative integer")
    return (factorial(n) - 1).bit_length()


for n in (0, 1, 2, 4, 8, 16):
    print(f"n={n}: at least {comparison_lower_bound(n)} comparisons")
text
n=0: at least 0 comparisons
n=1: at least 0 comparisons
n=2: at least 1 comparisons
n=4: at least 5 comparisons
n=8: at least 16 comparisons
n=16: at least 45 comparisons

该计数只说明叶子至少需要多少空间,未保证能用合法的两元素比较把树恰好构造成最小高度。算法允许比较相等也不会推翻证明,因为我们选取了互异键的输入子集。 MIT 比较模型与排序

对总是正确的随机算法,可固定随机选择得到确定性树。若各叶深度为 did_i,这些路径互不为前缀,故 ∑i2−di≤1\sum_i 2^{-d_i}≤1。由指数函数的凸性,均匀互异排列的平均深度至少为 log⁡2(n!)\log_2(n!)。再对随机选择取期望,至少有一个输入的期望比较次数不低于这个下界。

为什么有时可以线性排序

计数排序可以直接用受限整数键索引计数数组。若键域大小为 KK,典型代价为 Θ(n+K)\Theta(n+K),在 K=O(n)K=O(n) 的条件下是线性的。基数排序还取决于需要处理的位数和每轮成本,桶排序的效果依赖分布及桶内工作。它们利用了比较模型没有授予的操作。下一章从计数排序开始,检查这些条件如何进入复杂度。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

比较排序下界

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通