算法设计与分析导论：问题建模、正确性与算法选择

给一间会议室安排活动，可以问“最多安排多少场”，也可以问“怎样安排才能获得最高收益”。两句话使用相同的时间数据，却规定了不同的正确答案。

算法设计从这样的区别开始：先把问题说清楚，再研究求解步骤是否正确、运行需要多少资源，最后把步骤实现成程序。

本文介绍问题建模、算法正确性与方法选择。适合已经接触变量、循环和数组的读者；读完能够写清一道题的输入、输出、约束与目标，并组织一次完整的算法分析。

1. 先区分问题、算法和程序

1.1 问题规定“什么结果算正确”

假设有一个会议室，若干活动都想使用它。一个完整的问题至少要说清四件事：

项目	本例中的含义
输入	每个活动的开始时间和结束时间
输出	被接受的活动编号集合
可行性约束	被接受的活动不能占用同一时刻的会议室
优化目标	被接受的活动数量最多

约束还要说明活动是否允许拆分、端点相接是否兼容，以及是否预留清场时间。具体的半开区间约定与兼容条件，在贪心算法的区间模型中展开。

“同一个输入对应确定的答案含义”，不等于“同一个输入只能有一份合法方案”。 课件用输入到输出的函数帮助理解问题，但优化问题可能存在多份同样最优的解。不同程序输出不同的最优方案，也可能都正确；若接口要求结果唯一，需要额外规定平局时的选择规则。

1.2 算法规定“按照什么步骤求解”

对同一个调度问题，可以提出不同算法：

枚举所有活动子集，逐一检查，再选数量最多的。
每次选最早开始的活动。
每次选最早结束的活动。

这些都是明确的操作思路，但它们不一定都正确，也不一定同样高效。

算法通常需要输入、输出、明确且可执行的步骤，并在规定的合法输入上有限终止。伪代码便于表达思路，暂时不必纠结某种语言的语法。

1.3 程序是算法的具体实现

同一个贪心算法可以用 Python、C++ 或 Java 实现。但实现还会引入类型、排序稳定性、边界条件、溢出和数据结构等问题。

从问题模型到算法再到程序的流程，以及正确性和复杂度的检查位置

可以分别检查两层正确性：算法在数学上是否能解决问题；程序是否忠实实现了这个算法。编译通过只能说明语法等检查通过，不能替代这两层判断。

2. 判定、最优值、最优解与数值计算

课件把问题分为判定、优化和数值计算几种类型。优化问题中，又要区分“最优值”和“最优方案”。

以带权区间调度中的一个实例说明：

问题形式	提问方式	输出形式
判定问题	是否存在总收益至少42的兼容方案？	是或否
最优值问题	最大总收益是多少？	42
最优解问题	哪些任务能实现这个最大收益？	任务 d、h

知道最优值是42，并不自动等于已经知道选哪些任务。动态规划篇会进一步说明怎样从最优值恢复任务方案。

反过来，有了一个最优方案，通常可以直接计算它的目标值。对整数目标且已知上下界的问题，也常能把优化问题与多次判定联系起来，但需要分析调用次数与数值编码长度，不能无条件认为两种形式完全相同。

数值计算则可能要求求出具体数值。例如：

$$ 2x+y=5,\qquad x-y=1 $$

消去变量得到 $x=2,y=1$。更一般的数值问题还要说明允许误差、数值稳定性和精度要求；“输出一个数”不代表可以忽略这些要求。

3. 终止性、正确性与资源消耗

3.1 算法为什么会结束

每轮处理一个未处理活动，活动数量有限，因此处理完毕就能结束。若步骤写成“不断尝试，直到找到最优方案”，还需要给出识别最优方案的方法，以及最终能够停止的理由。

终止性常由一个不断变化的量说明：未处理元素数量每轮减少，或扫描下标不断增加并受到数组长度限制。

3.2 算法为什么正确

正确性要求：对每个合法输入，算法输出都满足问题定义。优化问题还要求输出达到目标的最优值。

可以分开检查：输出是否可行，目标是否最优，程序是否忠实实现了步骤。编译通过说明语法等检查通过；测试用来发现实现错误；数学证明说明对全部合法输入成立的理由。

常见证明方法有循环不变式、归纳法和交换论证。它们分别在扫描、递归或贪心等场景中提供可检查的论证结构。贪心篇会用具体问题展开交换论证。

3.3 为什么要分析时间和空间

同一个问题可能有多种正确算法。它们得到同样的答案，处理大输入时的资源消耗却可能相差很大。

时间分析研究需要执行多少工作，空间分析研究运行时同时保存多少数据。活动数量、数组长度、图的顶点数和边数都可能成为规模参数。实际秒数还受到硬件、语言和数据分布影响。

从代码统计操作次数、比较辅助空间的方法，见复杂度分析基础；渐进符号的严格定义放在渐进符号与函数增长率。

4. 怎样考虑算法策略

先观察问题结构，再挑选能够利用这种结构的方法。

算法方法	主要思想	适用场景示例与后续文章
枚举	尝试所有候选方案并检查	小规模子集搜索，见代码计数
贪心	每一步选择一个当前最有利的候选	无权活动选择与一维覆盖
动态规划	定义子问题，保存并复用答案	带权区间调度
图算法	用顶点和边表达关系约束	人员与岗位的匹配、冲突独立集
近似与启发式	根据效率与解质量要求选择保证	困难问题求解方法

例如，无权区间调度利用时间轴上的结束顺序；带权调度还需要比较不同子问题的收益；人员岗位分配适合用二分图表示。目标或约束改变后，应重新分析原来的理由是否仍成立。

5. 面对一道算法题的分析流程

明确输入和输出：输入有哪些字段，输出是数值、方案还是是/否。
确定合法输入和约束：范围、重复值、空输入、端点和拆分规则。
明确目标：返回任意可行方案、最优值，还是实际最优方案。
考虑策略：从一个容易验证的枚举算法出发，寻找顺序、局部结构或可复用的子问题。
分析正确性：分别说明终止、可行与最优。
分析资源：确定规模参数，统计时间和同时存活的额外数据。
编写程序并测试：对照手算结果，检查边界与随机小实例。

可以先写一份“问题说明”，再写伪代码，最后实现。模型明确后，才能区分算法设计上的错误与程序实现上的错误。

6. 练习

练习1：问题形式

“有没有总收益至少40的兼容方案？”“最大收益是多少？”“请返回实现最大收益的任务编号。”分别属于什么问题？只输出42，能否完整回答第三个问题？

练习2：模型边界

给活动安排增加“相邻活动之间留1单位准备时间”的约束，输入、可行性条件与目标中，哪些需要修改？

练习3：正确性与资源

两个程序都返回合法方案，其中一个在三组测试上更快。能据此认定它对所有输入都最优、对所有规模都更快吗？还需要分别分析什么？

7. 参考答案

依次是判定问题、最优值问题和最优解问题。第三问要求实际方案，仅返回42还缺少任务编号。
可以继续输入开始、结束时间；准备时间成为模型中的额外参数或固定约定。可行性要要求前一活动结束加1不晚于后一活动开始；“数量最多”的目标可以保持不变。
合法方案说明可行性，最优性需要排除更好的合法方案；有限测试的秒数反映特定运行条件，规模增长规律还需时间分析。额外空间也是单独的比较维度。

8. 后续学习

顺序	文章	核心问题
2	算法复杂度分析基础：从代码计数到时间与空间复杂度	怎样从代码计数，并区分时间与空间？
3	渐进符号与函数增长率：Big-O、Ω、Θ 与严格比较	怎样严格描述和比较增长阶？
4	贪心算法入门：从局部选择到全局最优证明	局部选择为什么能组成全局最优解？
5	动态规划入门：从状态定义到最优方案恢复	怎样定义状态、复用答案和恢复方案？
6	图上的组合优化：二分图匹配与独立集	怎样用图表示分配和冲突？
7	计算复杂性入门：P、NP、NP完全与困难问题求解	求解、验证、归约与困难性有什么区别？

下一篇：算法复杂度分析基础：从代码计数到时间与空间复杂度。完整路线也可在算法设计与分析学习路线中查看。

参考资料

《Design and Analysis of Algorithms》第一讲 Introduction，第15至20页的问题、问题形式与算法设计目标，以及第27至32页的典型问题。活动安排作为贯穿专题的案例，各算法的推导与代码在对应文章展开。