CSCI3160 L01 · Part 2/3 重试直到成功

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L01，第 2 部分 / 共 3 部分 · 原件 L01-Recursion-Repeating-Geometric-Series-未核.pdf（本地课件） p.10–15 定位：理解秩、答案保留和拒绝重试，算清一次成功概率及本层期望工作。前后：上一份 Part 1 · 下一份 Part 3

Repeating till Success

p.10 分节页。

选择与秩（p.11–12）【新】

题面（同原件 · k-Selection · p.11）

p.11 The k-Selection Problem: You are given a set S of n integers in an array and an integer $k\in[1,n]$ . Find the k-th smallest integer of S.

For example, suppose that S = (53, 92, 85, 23, 35, 12, 68, 74) and k = 3. You should output 35.

p.11 要一个次序统计量，不要求全部排序。算一遍：讲义八个数排序为 12、23、35、53、68、74、85、92，第三个是 35；排序只是核对答案，不是随后算法的步骤。

p.12 The rank of an integer $v\in S$ is the number of elements in S smaller than or equal to v.

p.12 的秩（rank）是一个计数。53 前面连同自身有 12、23、35、53 四个元素，所以秩为 4；12 的秩为 1。扫描数组、累计不大于 $v$ 的元素即可求秩，每个元素检查一次，代价 $O(n)$ 。讲义采用集合；补充：若实现改成允许重复值的数组，不能再直接假定“每个秩对应一个等概率枢轴”，应另外处理等于枢轴的整组元素。

保留答案，同时缩小问题（p.13–14）【新】

p.13 Task: Assume n to be a multiple of 3. Obtain a subproblem of size at most $2n/3$ with exactly the same result as the original problem.

p.13 要同时保留三个条件：新集合够小、新秩合法、新答案与旧答案相同。只丢掉很多元素，却忘记更新秩，仍然是错误算法。

p.14 随机取枢轴 $v$ ，令 $S_1$ 为不大于它的元素、 $S_2$ 为大于它的元素。如果 $k\le\lvert S_1\rvert$ ，目标在左边，保留 $S_1$ 与 $k$ ；否则保留右边，并减去被丢弃的较小元素个数。

反复执行：
  从 S 均匀随机选择 v
  分成 S1（不大于 v）与 S2（大于 v）
  若 k <= size(S1)：候选子问题为 (S1, k)
  否则：候选子问题为 (S2, k-size(S1))
  只有候选规模不超过 2 size(S)/3 时，才接受本次缩减

算一遍：用 p.11 的集合与 $k=3$ ，枢轴 53 使左集合为 {53,23,35,12}，大小 4，新秩仍为 3，满足 $4\le16/3$ ，目标仍是 35。若枢轴是 23，保留右侧六个数，新秩为 $3-2=1$ ，答案依然是 35，但 $6>16/3$ ，这轮缩减失败，需要从原问题重新抽枢轴。失败指“缩得不够”，不指“答案错了”。

补充：失败的这一轮究竟保留什么？ 以刚才枢轴 23 为例，候选六元素集合确实含答案，但课堂子程序拒绝它的原因是规模保证未达标。下一次应以原八元素问题重新取样，而不是悄悄以六元素集合重试，再仍用原八元素的成功概率证明。可以设计另一种正确算法，但那需要另一份成本分析。

一次尝试的输入 (S,k) 在成功返回前保持不变；临时分组和计数可以丢弃或复用缓冲区。接受后，新调用才接管较小的集合。这样重试内存不会随着失败次数无限堆积。计算右侧新秩时，减去的是所有不大于枢轴的元素数，包括枢轴本身。

自测：原八个数找第 6 小，若枢轴为 53，新问题是什么？

先数不大于 53 的四个数，再从原第六名扣除它们。新集合为 {92,85,68,74}，新秩为 $6-4=2$ ，其中第二小是 74。核对原有序序列的第六项也是 74。若保留右侧却不改 k，新秩 6 超过集合大小 4，连子问题的合法输入条件都破坏了。

成功概率与期望重试次数（p.15）【新】

p.15 Lemma: The algorithm succeeds with probability at least 1/3.

当枢轴秩 $r$ 在 $[n/3,2n/3]$ 内，左边大小 $r\le2n/3$ ，右边大小 $n-r\le2n/3$ 。无论目标在何侧，保留的那侧都足够小。p.13 假设 $n$ 是 3 的倍数，因此中间这段至少有 $n/3$ 个秩；集合元素均匀抽取，成功概率至少 $1/3$ 。

由本页展开一般“成功概率至少 c”的结论：若每次独立尝试成功概率为 p，且 $p\ge c>0$ ，失败 j 次的概率为 $(1-p)^j$ 。首次成功所需次数 N 满足

E[N]=\sum_{j=0}^{\infty}P(N>j) =\sum_{j=0}^{\infty}(1-p)^j =\frac{1}{p}\le\frac{1}{c}.

尾和从 j=0 开始，因为至少会试一次。p.15 取 c=1/3，所以至多三次是期望上界，不是第三次必须成功；失败四次的事件仍有正概率。

每次尝试扫描并分区需要 $O(n)$ 。失败后原问题没变，重新独立抽样，期望尝试至多 3 次，所以本层期望成本仍是 $O(n)$ ，不是 $O(3^n)$ 。补充／算一遍（数字是我为演示取的，讲义没给）：取 $n=12$ ，秩 4、5、6、7、8 共五种都能保证最多保留 8 个数，概率至少 $5/12\ge1/3$ ，故用较宽松的“三次期望上界”是安全的。

考试角度：（A 级：Quiz-01-2025T1-题解.pdf Q2，考缩减阈值改变后成功概率与总期望时间；演练见附录 A2）。

本讲核心考点

选择问题保留答案时还要调整秩（p.11–14；C 级）。
中间秩保证固定成功概率，从而本层期望线性（p.15；A 级：Quiz-01-2025T1 Q2）。

附录

A2 作业/往年题演练（非讲义内容）：改变缩减阈值

题面（Quiz-01-2025T1-题解.pdf · Q2(a)(b) · p.2）

p.2 2. Recall the randomized algorithm for k-selection introduced in the lecture. Given an array S of size n and a target rank k, it repeatedly invokes a randomized subroutine Asub that reduces the problem size by a factor of 2/3 at each step. The pseudocode for Asub is shown in Algo. 1 below.

Algorithm 1: The Randomized Sub-Algorithm Asub Input: An array S and a desired rank k.

Take an element $v\in S$ uniformly at random.

Divide S into S1 and S2 where S1 = the set of elements in S less than or equal to v; S2 = the set of elements in S greater than v.

If $\lvert S_1\rvert\ge k$ , then return $S'=S_1$ and $k'=k$ ; else return $S'=S_2$ and $k'=k-\lvert S_1\rvert$ . The algorithm succeeds if $\lvert S'\rvert\le\frac{2}{3}\lvert S\rvert$ , or fails otherwise. Repeat the algorithm until it succeeds.

We now modify Algo. 1 by changing the success condition from “ $\lvert S'\rvert\le\frac{2}{3}\lvert S\rvert$ ” to “ $\lvert S'\rvert\le\frac{9}{10}\lvert S\rvert$ ” while keeping everything else the same. Answer the following questions regarding this modified version: (a) (20 points) Recall that we proved in lecture that a single run of the original Algo. 1 succeeds with probability at least 1/3. After the modification above, what lower bound can we give for the success probability? Provide a formal proof of your answer. (b) (10 points) Recall that we proved in lecture that the randomized k-selection algorithm using Algo. 1 runs in O(n) expected time. Now, if we replace Algo. 1 with the modified version in this k-selection algorithm, what would its expected running time be? Please provide an explanation for your answer.

公式按原题重排。按题解采用的分段比例分析，秩在 $[n/10,9n/10]$ 的枢轴两边均不超过 $9n/10$ ，故成功概率下界写为 $4/5$ 。因此每层期望重试至多 $5/4$ 次；一轮扫描成本至多 $an$ 时，每层期望不超过 $5an/4$ 。递归规模按 $9/10$ 衰减：

\sum_{j=0}^{\infty}\frac{5a}{4}n\left(\frac{9}{10}\right)^j =\frac{25a}{2}n=O(n).

**补充：整数边界。**上面的 $4/5$ 是官方题解给出的比例下界，严谨应用须处理离散秩与小规模。例如 $n=2,k=2$ 时，只有秩 1 的枢轴成功，概率为 $1/2$ 。一般精确成功数为

\max(0,\lfloor0.9n\rfloor-k+1) +\max(0,k-\lceil0.1n\rceil),

两项分别数 $r\ge k$ 且 $r\le0.9n$ ，以及 $r<k$ 且 $r\ge0.1n$ 。除以 $n$ 即为概率；在 $n$ 为 10 的倍数时前面的下界安全，对任意 $n$ 可用 $0.8-1/n$ 的保守下界，并将固定小规模直接求解。这样总期望仍为线性。

回到正文：成功概率与期望重试次数（p.15）

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L01-Recursion-Repeating-Geometric-Series-未核.pdf（本地课件），本部分 p.10–15；页码均为 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：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。