· 算法设计与分析
算法设计与分析 Day1:从问题定义到正确性与效率
RedMoon · 2026-09-17 · 课堂阅读笔记
做出一个答案,等于解决一个问题吗
Problem 与 Instance 的区别在于:问题定义一整类输入及其期望输出,实例是其中一个具体输入。“返回一组数的最大值”是问题,“在 5、4、3、2、1 中返回 5”是实例。程序通过样例之后,还需要论证它为什么适用于其他合法输入。
课程的训练因此有两个部分:设计一个明确的计算过程,再分析它是否正确、需要多少时间与空间。正确性讨论所有满足前提的输入;复杂度讨论规模增长时资源如何变化,不只是一次运行用了几毫秒。
可计算性与可行性
课件用希尔伯特第十问题引出算法边界:是否存在一个通用算法,判断任意整系数多项式丢番图方程是否有整数解?1970 年完成的否定结果说明,不存在解决这一整类判定问题的通用算法,而不是说每一个具体方程都不能求解。
例如课件列出的 $3x^2-2xy-y^2z=7$,代入 $x=1,y=2,z=-2$,得到 $3-4+8=7$,确实是一组解。水果方程图示用简单外观与巨大整数解之间的反差说明直觉不可靠,不能由此推出所有类似方程都困难或不可判定。
丘奇-图灵论题把直觉上的有效可计算过程与图灵机可计算性联系起来。不同形式模型之间可以证明等价,但涉及非形式化“有效方法”的论题本身,不是通过一个普通形式定理直接证明的。现实计算机有限,而理论模型可按需要扩展存储,这个抽象也要分清。
可计算并不意味着现实预算内算得完。课程主要进入的下一层问题是:已知能计算,怎样设计更有效的算法,并说明为什么有效。
用四段式写清算法
课件要求 Lecture Notes 按 Problem、Instance、Algorithm、Analysis 组织。Algorithm 包括先备知识和算法陈述;Analysis 包括正确性、时间与空间分析。
例子一:求最大值
Problem:输入非空数组 $a_1,\ldots,a_n$,输出最大元素。Instance:输入 $(5,4,3,2,1)$,输出 5。
Algorithm:初始化 $S=a_1$,依次检查 $a_2$ 到 $a_n$;遇到更大值就更新 $S$,最后返回它。非空是前提,不能在空数组上直接读取首元素。
Analysis:循环不变式为“处理完前 $i$ 个元素后,$S$ 等于该前缀最大值”。初始化在 $i=1$ 时成立;处理下一个元素时取旧最大值与新元素的较大者,保持成立;结束时覆盖整个数组,因此结果正确。算法进行 $n-1$ 次比较,时间为 $\Theta(n)$,额外空间为 $O(1)$。若输入任意且只通过比较获知大小,每个非最大元素至少输掉一次比较,也给出 $n-1$ 次比较的下界。
三道题里的不同结构
课件中的三道题分别涉及不同的信息维护方式。
| 问题 | 实例与结果 | 算法结构及关键条件 |
|---|---|---|
| 121 买卖股票的最佳时机 | [7,1,5,3,6,4],最大利润 5 |
一次交易,买入在卖出之前;维护历史最低价与最佳非负收益 |
| 724 寻找数组的中心下标 | [1,7,3,6,5,6],返回下标 3 |
总和减去左侧和与当前值,得到右侧和;从左到右找首个相等位置 |
| 643 子数组最大平均数 I | [1,12,-5,-6,50,3],k=4,结果 12.75 |
固定长度窗口,维护窗口和;每次移出旧值、移入新值 |
三题都可做到线性时间、常数额外空间,但不能仅因复杂度相同就认为思路相同。股票题维护历史最优,中心下标题利用左右和关系,滑动窗口利用相邻候选高度重叠。最后一题最优窗口和为 $12-5-6+50=51$,平均值为 $51/4=12.75$;初始化应使用真实首窗口,而不是零,否则全负输入可能出错。
假币问题:信息容量不是构造证明
十二枚硬币中有一枚重量不同,可能偏轻也可能偏重,候选状态有 $12\times2=24$ 种。天平一次有左重、平衡、右重三种结果,三次称量最多产生 $3^3=27$ 条结果路径。
$27\geq24$ 是信息容量上的必要检查,不单凭它就证明一定存在合法称量方案。还要构造每一步实际可执行的称量,保证不同候选可区分。它是三分结果的决策树,不应叫二分搜索。下界分析、容量计数和具体算法分别回答不同层次的问题。
秘书问题:先建立基准,再做不可撤销选择
秘书问题把算法放进信息受限的环境:候选人以均匀随机顺序到来,能力排名互异,只能比较已见候选,面试后立即决定,拒绝后不能回头,目标是选中全体最优者。观察期的长度可在这些假设下推导。
考虑阈值策略:前 $r$ 人只观察不录用,记录最佳;之后录用第一个超过此前所有人的候选。若再没有破纪录者,按约定结束或在末尾兜底;这不会改变选中全体最优者的下面计算。
假设最优者出现在第 $t>r$ 位。成功需要前 $t-1$ 人中的最佳出现在观察期,否则此前已遇到破纪录者并做出选择。其概率为 $r/(t-1)$,而最优者每个位置的概率为 $1/n$。于是:
\[P_n(r)=\sum_{t=r+1}^{n}\frac1n\frac{r}{t-1} =\frac rn\sum_{j=r}^{n-1}\frac1j,\qquad 1\leq r<n.\]当 $n$ 较大,令 $x=r/n$,用积分近似调和和:
\[P_n(r)\approx\frac rn\ln\frac nr=x\ln\frac1x.\]求导得到 $-\ln x-1=0$,故最优阈值比例趋近 $1/e$,成功概率也趋近 $1/e\approx0.368$。这里的对数是 $\ln(n/r)$,不是 $\ln n$;有限 $n$ 应比较整数阈值,不能把极限写成任意有限规模下精确相等的概率或普适上界。
在经典相对排名模型中,这个阈值策略具有最优性结论;若知道候选绝对能力的分布、允许回选、多次选择或顺序不是随机,问题模型已改变,不能原样搬用结论。课件提示的大规模结论因此应与假设一起记忆。
课程安排与论证要点
课件列出平时 30%、期中 20%、期末 50%。平时涉及作业、小组 Lecture Notes 和课堂表现,其中课堂表现占总成绩 5 分。课程内容从插入排序、归并排序开始,进入子数组、主定理、整数乘法,再到快速排序、堆排序、决策树、动态规划、贪心、Huffman 与图算法;安排以正式通知为准。
算法分析需要可检查的论证:问题前提是什么?算法维护了什么结构?证明对全部合法实例成立吗?资源分析是否把输入存储与额外空间分开?秘书问题还说明,信息的获得方式本身也是问题定义的一部分。
复习要点
- 分别举例说明问题、实例、算法与程序的关系。
- 准确表述希尔伯特第十问题的否定结论。
- 用初始化、保持、终止三个步骤证明求最大值的循环不变式。
- 手算三道截图题,并检查全负数组、首尾下标和交易先后等边界。
- 解释假币计数为什么是必要检查,而不是完整方案。
- 重推秘书问题的调和和式与 $1/e$ 极限,说明随机顺序假设。