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

确定性线性选择

确定性线性选择

随机化快速选择通常很快,但理论上仍可能连续遇到极差枢轴。确定性线性选择通过“五元素分组”和“中位数的中位数”选择枢轴,使每轮都能排除足够多的元素,从而把最坏时间复杂度保证为 O(n)O(n)。

学习目标

  • 理解五元素分组如何构造质量可证明的枢轴。
  • 能够实现支持重复元素的确定性选择算法。
  • 能够根据递推关系解释最坏线性时间的来源。

枢轴构造与执行流程

算法先把当前序列按最多五个元素一组切分,对每组排序并取中位数,再递归选择这些中位数的中位数作为枢轴。随后按照“小于、等于、大于枢轴”分成三部分,只在包含目标下标的部分继续递归。

确定性线性选择的五元素分组流程

选择五个元素一组并不是随意规定。设组数 g=⌈n/5⌉g=\lceil n/5\rceil,偶数组数时取中间偏右的组中位数。两个方向至少各有 ⌊g/2⌋\lfloor g/2\rfloor 个组中位数符合不大于或不小于枢轴。每个完整组贡献至少三个符合方向的元素,最多扣掉一个不满五个元素的组。因此两个方向各至少有 3(⌊g/2⌋−1)3(\lfloor g/2\rfloor-1) 个元素,保留的严格一侧至多为 7n/10+67n/10+6。重复值也符合这个非严格计数,并可通过等值区间一次排除。

三路划分对重复值尤其重要。若目标落在“等于枢轴”的区间,算法可以立即返回,不会因大量重复元素而反复递归。

最坏线性时间为何成立

设处理 n 个元素的最坏时间为 T(n)。寻找各组中位数需要线性工作,递归寻找中位数的中位数处理约 n/5 个元素,主递归最多处理约 7n/10 个元素,因此可以写成:

T(n)≤T(⌈n/5⌉)+T(⌊7n/10+6⌋)+cnT(n) \le T(\lceil n/5 \rceil) + T(\lfloor 7n/10 + 6\rfloor) + cn

这里用 T(n) 表示规模至多 n 的最坏成本,c 是本层线性工作的常数。两个递归规模相加至多 0.9n+70.9n+7,当 n≥140 时至多 0.95n0.95n。用 T(n)≤CnT(n)\le Cn 强归纳,取 C≥20cC\ge20c 并覆盖较小规模,代入得到 0.95Cn+cn≤Cn0.95Cn+cn\le Cn。这给出固定单位比较成本下的最坏线性上界。与随机化快速选择相比,这种保证不依赖输入排列或随机运气,但常数因子更大,工程中通常只在需要最坏情况保证时采用。

本例每层用线性额外空间保存分组和分区。两次递归依次执行,任一时刻只保留一条调用路径,较大规模下每层长度按固定比例缩小,因此峰值辅助空间为 O(n)。通过原地分区可以降低额外空间,但实现会明显复杂。

完整可运行示例

将下面代码保存为 deterministic_select_demo.py。参数 k 仍按从 1 开始计数。

python
from typing import List

def deterministic_select(values: List[int], k: int) -> int:
    if type(k) is not int or not 1 <= k <= len(values):
        raise ValueError("k 必须位于 1 到数组长度之间")

    return select_by_index(values, k - 1)

def select_by_index(values: List[int], target: int) -> int:
    if len(values) <= 5:
        return sorted(values)[target]

    groups = [values[index:index + 5] for index in range(0, len(values), 5)]
    medians = [sorted(group)[len(group) // 2] for group in groups]
    pivot = select_by_index(medians, len(medians) // 2)

    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]

    if target < len(lower):
        return select_by_index(lower, target)

    equal_end = len(lower) + len(equal)
    if target < equal_end:
        return pivot

    return select_by_index(higher, target - equal_end)

def main() -> None:
    numbers = [12, 3, 5, 7, 4, 19, 26, 1, 8, 15, 11, 2, 10, 6, 9]

    for k in (1, 8, 15):
        result = deterministic_select(numbers, k)
        print(f"第 {k} 小元素: {result}")

if __name__ == "__main__":
    main()

运行命令如下:

bash
python deterministic_select_demo.py

预期输出

text
第 1 小元素: 1
第 8 小元素: 8
第 15 小元素: 26

常见错误与练习

常见错误是直接把每组中位数的普通平均值当作枢轴。算法需要的是“中位数集合中的中位数”,必须递归执行选择,而不是计算算术平均数。最后一个不足五个元素的组仍可参加代码中的枢轴选择。推导每个完整组贡献三个元素时,应将这个组扣除。

练习一:为函数加入比较次数统计,并与上一课的随机化快速选择在相同输入上比较。验收条件是两种算法都返回相同答案,并分别输出比较次数。

练习二:构造包含大量重复值的数组,验证三路划分能够直接覆盖目标位置。验收条件是查询最小值、中位位置和最大值时均返回正确结果。

本课总结

  • 五元素分组让枢轴两侧都能排除可证明数量的元素。
  • 递推式中两个递归规模比例之和小于 1,因此最坏时间为 O(n)O(n)。
  • 三路划分可正确处理重复值,但当前实现以 O(n)O(n) 额外空间换取清晰性。

下一课预告

完成线性选择后,下一阶段将把分区、顺序统计量与查找方法结合起来,进一步比较不同输入条件下的算法选择与工程权衡。

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

目录与阅读设置

阅读设置

17

记录一个想法

确定性线性选择

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

登录哪都通