CSCI3160 L00B 最坏输入与最坏期望

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L00B 最坏输入与最坏期望 · 原件 L00B-Warmup-02-Worst-Case-Analysis-未核.pdf（本地课件） p.1–11 定位：把输入的差异与算法内部随机性分开，算清二分查找和随机找零的保证。承接：#L00A-04 固定输入上的随机代价

p.1 标题页。

为什么比较最坏输入（p.2–3）【延伸 L00A p.14–16】

p.2 One approach—the one we follow in this course—is to look at the algorithm’s cost on the worst input, as we will formalize in this lecture.

p.2 选择最坏输入，是为了使保证覆盖所有合法数据，不需要假定现实数据的分布。规模相同不等于难度相同：找一个马上能找到的数和证明另一个数不存在，可能花不同时间。

p.3 The worst expected cost of A under the problem size n is the maximum $E[X_A(I)]$ of all $I\in I_n$ .

公式按讲义重排。p.3 的 $I_n$ 是所有规模为 $n$ 的合法输入的集合； $I$ 是其中某个输入； $X_A(I)$ 是算法 $A$ 在这个输入上的代价。确定性最坏代价是对输入取最大。随机算法的最坏期望则为

\max_{I\in I_n} E[X_A(I)].

先固定 $I$ ，只对随机选择取平均；再找平均代价最大的输入。补充／算一遍（数字是我为演示取的，讲义没给）：两个合法输入的随机代价分别恒为 5，以及以相等概率为 2 或 10。它们的期望是 5 和 $(2+10)/2=6$ ，最坏期望为 6；所有可能执行里的最大代价却是 10。两个量回答不同问题。

补充：两个量词的顺序不能交换。 把算法掷出的随机结果记作 $R$ ，则输入是先固定的，观察者不能看见 $R$ 后再临时更换输入。自取一个只有两种输入、两种等概率随机结果的例子：

固定输入	R=0 的代价	R=1 的代价	本输入上的期望
I₁	0	10	5
I₂	10	0	5

先对每行平均，再选最大得到 5；如果每次先看随机列，再挑该列最坏输入，两列的最大值都是 10，平均得到 10。后者允许输入跟着随机选择变化，已经不是本讲的最坏期望。该表只是解释量词的代价例子，不是具体 RAM 程序的逐指令实现。

自测：数组至少一个零，若连续 n 次没找到，能否判定算法错了？

不能。若恰有一个零，连续 $n$ 次失败的概率是 $(1-1/n)^n$ ，在 $n>1$ 时仍为正。期望 $n$ 次不是超时界。若题目要求保证有限步终止，可以扫描数组，但其最坏时间就按扫描重新分析，不能保留“随机半数零常数期望”的描述来充当扫描成本。

字典查询的输入和实例（p.4–5）【新】

题面（L00B-Warmup-02-Worst-Case-Analysis-未核.pdf · Dictionary Search · p.4）

p.4 Problem Input: In the memory, a set S of n integers have been arranged in ascending order at the memory cells from address 1 to n. The value of n has been placed in Register 1 of the CPU. Another integer v has been placed in Register 2 of the CPU.

Goal: Determine whether v exists in S.

p.4 规定数组已经有序，因此后面分析不含排序费用； $n$ 是元素个数，输入则是数组与目标值这一个整体。

图（p.5）：同一数组上的 yes-input 与 no-input。元素：数组为 5、9、12、17、26、28、35、38、41、47、52、68、69、72、83、88；两个寄存器分别给出 16 与目标 35，或 16 与目标 36。看什么：上图能在第 7 格找到 35，下图要证明 36 不在数组中；同为规模 16 的合法输入。

二分查找为什么是对数时间（p.6）

p.6 The worst-case cost of the binary search algorithm is $O(\log n)$ .

每比较一次中间元素，就能丢弃不可能含目标的一半：目标比中间值小，右半全不合适；反之丢左半。连续减半约 $\log_2 n$ 次后只剩常数规模，每轮只有常数次地址计算、读取和比较，所以原子操作总数是对数量级。

算一遍：用 p.5 数组查询 35，取区间中点向下整：先读第 8 格 38，保留 1–7；读第 4 格 17，保留 5–7；读第 6 格 28，保留 7；读第 7 格 35，四次比较找到。查 36 时前三步相同，第四次读到 35 后区间为空，返回不存在。这里数的是比较次数；RAM 总操作还包括地址与边界更新。

p.6 给的三个可能时间函数也可以逐个检查： $10(1+\log_2 n)$ 是常数项加对数项； $352\log_3 n$ 可用换底写为 $352\log_2 n/\log_2 3$ ；第三个是

\sqrt{\log n}+78\log_2(n^{83}).

对充分大的 n，第一项不超过常数倍的 $\log n$ ，第二项由幂次法则成为 $6474\log_2 n$ 。三者都在对数上界内，却都不必等于 $\log_2 n$ 。这里列出的是满足同一渐近上界的函数示例，不是声称二分查找在某个实现中精确执行这些步数。

讲义特别提醒 $O(\log n)$ 不是精确等式：常数倍、底数改变和低阶项都可能不同。因此不能把“规模 16”直接换算为“整个程序四个原子操作”。

至少一个零：期望取决于零的比例（p.7–8）【新】

题面（L00B-Warmup-02-Worst-Case-Analysis-未核.pdf · Example 2 · p.7）

p.7 /* A is an array of size n that contains at least one 0 */

do

r = RANDOM(1, n)

until A[r] = 0

return r

What is the expected cost of the algorithm?

p.7 中每次从所有位置重新抽取，可以重复抽到同一个非零位置。若数组有 $z$ 个零，合法条件给出 $1\le z\le n$ ，单次成功概率为 $p=z/n$ 。设期望抽样次数为 $t$ ：无论成功与否都已做一次抽样；以概率 $1-p$ 失败时，问题状态与抽样规则不变，还需要期望 t 次。因此

\begin{aligned} t&=1+(1-p)t,\\ pt&=1,\\ t&=1/p=n/z. \end{aligned}

这就是原页“期望重复 n 次”的来源。全是零时是 1 次；只有一个零时是 $n$ 次。每次抽样与检查只花常数步，因此相应时间分别为 $O(1)$ 与 $O(n)$ 。

p.8 Worst-case cost of the algorithm = $\infty$

p.8 Worst expected cost of the algorithm = $O(n)$

p.8 的两个结论可以同时成立：只要有非零位置，就存在任意长的失败串，所以所有执行无有限上界；但对每个合法输入求期望后，最差只是 $z=1$ 。算一遍：取 p.10 已给的八元素数组， $z=4$ ，期望抽样 $8/4=2$ 次；其中某次执行仍可能连续抽到位置 1、2、5、7 而失败四次。这没有违反期望为 2。

确定性算法的期望是什么（p.9）

题面（L00B-Warmup-02-Worst-Case-Analysis-未核.pdf · 思考题 · p.9）

p.9 Before proceeding, think: what is the “expected cost” of a deterministic algorithm?

固定输入后，确定性算法的代价是固定数 $t$ ，可以看作以概率 1 取 $t$ 的随机变量，所以期望仍为 $t$ 。不能对所有输入随便平均：题目没有给输入分布，本课的随机期望指算法内部随机性。

半数为零：随机化赢在哪里（p.10–11）【新】

题面（L00B-Warmup-02-Worst-Case-Analysis-未核.pdf · Find-a-Zero · p.10）

p.10 Problem “Find-a-Zero”: Let A be an array of n integers, among which half of them are 0. Design an algorithm to report an arbitrary position of A that contains a 0.

For example, suppose A = (9, 18, 0, 0, 15, 0, 33, 0). An algorithm can report 3, 4, 6, or 8.

p.10 只要求任意一个合法位置，不要求找最左零、所有零或某个特定零。这让均匀抽样可以利用“好位置有一半”的保证。

p.11 The algorithm finishes in $O(1)$ expected time on every input A!

p.11 使用 p.7 的算法，所有合法输入都有成功概率 $1/2$ ，所以期望轮数恒为 2，与 $n$ 无关。确定性方法则有固定的探查策略：在最坏情况下，前 $n/2$ 个不同的被探查位置都可以是非零，而仍有一个与此前观察一致的合法数组。至少要做线性数量的探查才能排除这种情况；顺序扫描又给出线性上界，因此问题的确定性最坏复杂度是 $\Theta(n)$ 。

算一遍：p.10 的 $n=8$ 有四个非零数。若算法前四次恰好探查到这四个位置，它仍没读到零；根据“恰好四个零”的承诺，可以推断其余位置为零。这解释了下界为何写“至少 $n/2$ 个”，而不是忽略承诺强行要求再读第五个。

考试角度：（C 级通识）常见考法是构造确定性算法的最坏输入，再与随机算法对每个固定输入的期望比较；随机化并未提供每次执行都更快的承诺。

补充对应的往年题演练见附录 A1。

本讲核心考点

最坏期望先平均随机选择，再对输入取最大（p.3，C 级）。
二分查找依赖输入已排序，时间是量级而非精确操作数（p.4–6，C 级）。
半数为零时随机找零期望常数，确定性最坏需线性代价（p.10–11，C 级）。

附录

本讲所需过程已在正文展开。

A1 作业/往年题演练（非讲义内容）：找到奇数的期望时间

题面（Final-2025T1-题目.pdf · Q1(f) · p.1；扫描件，视觉读取）

p.1 “(f) (2 points) Let S be an array of n integers, among which at least one integer takes the value of 1. Consider the algorithm shown in Algorithm 1 for finding an odd number from S. Algorithm 1 runs in O(n) expected time.”

算法（题面，p.1，变量与步骤按原件）：FIND-ODD(S)；repeat：x←a uniform random integer from 1 to size(S)；until S[x] is odd；return S[x]。

设实际奇数有 z 个。至少有一个 1，故 z≥1。每轮成功概率 z/n，独立重抽的期望轮数 n/z≤n，每轮只读一个元素并判断奇偶，为常数时间，因此该判断为真。最坏的输入是只有一个奇数，此时期望恰为 n；但某次运行仍可能连续失败任意多次，不能把期望线性写成每次执行都有线性上界。

回到正文：本讲正文

来源与证据

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