CSCI3160 L01 · Part 3/3 几何级数与选择

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L01，第 3 部分 / 共 3 部分 · 原件 L01-Recursion-Repeating-Geometric-Series-未核.pdf（本地课件） p.16–20 定位：把每层缩减的规模相加，证明完整随机选择算法的线性期望时间。前后：上一份 Part 2

Geometric Series

p.16 分节页。

逐层变便宜的总和（p.17–18）【新】

p.17 A geometric sequence is an infinite sequence of the form $n,cn,c^2n,c^3n,\ldots$

公式按讲义重排。p.17 假设常数 $0<c<1$ 。把级数记为 $S$ ，则 $cS$ 是少了首项 $n$ 的同一个级数，所以 $(1-c)S=n$ ，得到 $S=n/(1-c)$ 。 $c$ 固定时分母是常数，因而总和为 $O(n)$ 。

算一遍：取本讲缩减因子 $c=2/3$ ，总和上界为 $n/(1-2/3)=3n$ 。若演示规模取 27（数字是我为演示取的，讲义没给），前四项为 27、18、12、8，总计 65，而无限和为 81。后层虽然数量多，每层却便宜；不能把每层都按原规模 27 收费。

p.18 再提出同一个选择问题：输入是 n 个整数构成的集合 S（以数组保存）和满足 $1\le k\le n$ 的整数 k，输出 S 的第 k 小元素。秩指不大于该元素的集合成员数。它不要求输出全部排序结果；本节把刚得到的求和工具用于完整算法。

三种技巧合成一个算法（p.19–20）

p.19 Think: How is this related to geometric series?

p.19 先用重试得到足够小而答案不变的子问题，再递归求这个子问题。由于只追目标所在的一侧，各层规模至多是 $n,(2/3)n,(2/3)^2n,\ldots$ 。这就是 p.17 的级数。

p.20 Solving the recurrence gives $f(n)=O(n)$ .

公式按讲义重排。p.20 中 $f$ 已经是期望时间： $f(n)\le an+f(\lceil2n/3\rceil)$ ，展开后各层期望成本相加，上界为常数倍 $n$ 。小规模需直接求解，防止取整后规模不下降；这是实现基本情形的作用。结果是线性期望时间，并没有把任何一次执行的最坏时间变成线性。

把完整过程放在同一个阅读单元中：

Select(S,k):
  若 size(S) <= 2：直接比较并返回第 k 小的元素
  n = size(S)
  反复尝试：
    在原 S 中均匀抽取 v
    S1 = 所有不大于 v 的元素；S2 = 所有大于 v 的元素
    若 k <= size(S1)：(nextS,nextK) = (S1,k)
    否则：(nextS,nextK) = (S2,k-size(S1))
    若 size(nextS) <= ceil(2n/3)：停止尝试
  返回 Select(nextS,nextK)

大小不超过 2 时直接求解是补足取整边界的实现约定：否则 $\lceil2\cdot2/3\rceil=2$ 可能接受不缩小的子问题。对 n≥3，这个阈值严格小于 n，故接受后递归会终止。

用原讲义八元素集合走到底，目标 k=3：抽到 53 时留下 {53,23,35,12}、新秩 3；在这个四元素集合抽到 23 时留下 {53,35}、新秩 $3-2=1$ ；两元素直接比较返回 35。随机取值序列是为展示的一条可能路径，数组与目标来自 p.11。每次保留集合中的新目标都对应原来的第 3 小，因此最后返回的不是近似答案。

忽略取整先看主成本，若本层期望至多 an，则展开得到

f(n)\le an+a(2n/3)+a(2n/3)^2+\cdots\le3an.

为使取整也严谨：每层向上取整多出的常数可以累积为常数倍的层数；规模至少按固定比例收缩到常数后终止，层数为 $O(\log n)$ ，这些附加成本仍为 $O(\log n)\subseteq O(n)$ 。因此取整不会改变线性期望结论。

补充：为何期望递推可以接上一个随机子问题。 接受后得到哪个集合由随机枢轴决定，因此不能把下一层误当成某个事先固定的实例。但定义 $f(m)$ 为所有至多 $m$ 元素合法实例的最大期望成本，就保证无论这次返回的是哪一个集合，后续条件期望都不超过 $f(\lceil2n/3\rceil)$ 。再对返回集合取平均，也不会超过同一个上界。本层重试的期望费用与后续费用相加，使用的是期望线性性，不要求两段耗时独立。

这里递归树实际只有一条保留路径。若把左右两边都递归求解，每层总规模会回到约 $n$ ，就不能再拿 $n+(2/3)n+\cdots$ 这条单链级数证明线性。

自测：规模每次只减 1，为什么不能照搬“每次变小所以线性”？

若每层扫描当前输入，成本为 $n+(n-1)+\cdots+1=n(n+1)/2$ ，是平方量级。几何求和依赖固定比例缩小；“严格变小”只保证终止，不保证线性总工作。比率若为 $1-1/n$ 且 n 是原规模，分母也不是固定常数，不能把它藏进 O 的常数中。

考试角度：（A 级（扫描件，视觉读取）：Final-2025T1-题目.pdf Q3，考用两次选择报告秩区间；演练见附录 A3）。

本讲核心考点

逐层规模几何衰减，总和为线性（p.17–20；C 级）。
两次选择加一次扫描报告秩区间（p.18–20；A 级：Final-2025T1 Q3）。

附录

A3 作业/往年题演练（非讲义内容）：报告秩区间

题面（Final-2025T1-题目.pdf · Q3 · p.2；扫描件，视觉读取）

p.2 3. (10 points) [From special exercise.] Let S be a set of n distinct integers, and $k_1$ and $k_2$ be arbitrary integers satisfying $1\le k_1\le k_2\le n$ . Suppose that S is given in an array. Give an O(n) expected time algorithm to report all the integers whose ranks in S are in the range $[k_1,k_2]$ . Recall that the rank of an integer x in S equals the number of integers in S that are at most x. [Hint: Feel free to use the k-selection algorithm, without specifying how it works.]

公式按原题重排。先用 p.19–20 的选择算法得到第 $k_1$ 小的值 $x_1$ ，再得到第 $k_2$ 小的值 $x_2$ 。扫描每个元素 $y$ ，当且仅当 $x_1\le y\le x_2$ 时报告它。

正确性来自元素互异：有序序列中的第 $k_1$ 到第 $k_2$ 项恰好是这两个值之间的元素。小于 $x_1$ 的秩不足，大于 $x_2$ 的秩超出；区间内的全部元素都在一次扫描中被报告，不遗漏也不重复。两次选择的期望成本相加仍是 $O(n)$ ，加一次线性扫描及至多 $n$ 次输出，总期望 $O(n)$ ；两次选择的随机代价不需要相互独立才能使用期望线性性。

用讲义 p.11 数组作核对，若所需区间为第 3 到第 5（这两个秩是演示补充），边界是 35 与 68，扫描报告 53、35、68，数量 $5-3+1=3$ 。题目没要求输出排序，所以不应另加一次排序。

回到正文：三种技巧合成一个算法（p.19–20）

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L01-Recursion-Repeating-Geometric-Series-未核.pdf（本地课件），本部分 p.16–20；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。