3. 学期概览¶
3.1. 学期概览¶
本课程的核心问题是： 给定一个问题，我们是否拥有（或者能否设计出）一个好的解法？ 我们所做的一切都以某种方式与这个核心问题相关联。 这里的"好"通常指的是"在问题允许的范围内尽可能高效"。
如果我们有一个问题和与之对应的某个解法，那么就需要一种机制， 让我们能够评估该解法是否良好。 这正是算法分析发挥作用的地方。 本模块不是对基本算法分析的复习。 它是对基本概念的从头重建。 你以前对算法分析的学习可能侧重于如何分析给定的程序或算法。 本课程中我们当然也会这样做。 但在本模块中，我们将聚焦于这样的问题：算法分析如何帮助我们 回答核心问题。
本讨论假定你大致熟悉基本的 算法分析 术语和概念。 其中包括对术语 问题、算法 与 程序 的定义。 其中包括下述概念： 上界、 下界、 增长率、最好情况、 最坏情况、 平均情况、 大 O 记法、 Omega 记法 和 Theta 记法。 必要的话，请在继续之前复习这些材料。
我们的问题必须定义得足够清晰，才能在计算机上求解。 （实际上，要求解一个问题，我们需要的不止是清晰的定义。考试周结束时， 我们将讨论一些不可计算的（也就是说无法求解的）问题——即使它们 的定义是清晰的。）
一个 问题 是一个 函数 （即输入到输出的映射）。 对于这个问题，我们有不同的 问题实例 （输入），每个实例都有其长度。 要求解一个问题，我们必须提供一个算法、把问题实例编码为算法的输入， 以及把输出编码为解。
一个 算法 执行这一映射。 所提出的算法必须对所有实例都有效 （对每个输入实例给出正确的映射输出）。 （实际上，之后当我们讨论近似算法和概率算法时，将放宽这一限制。）
我们的目标是以尽可能少的计算代价求解每个问题实例。 我们最经常感兴趣的是解"大的"问题实例 （渐近分析）。 偶尔我们也会关注小实例。 这时，常数就很重要了。
归根结底，我们想通过一个高效的 程序 来求解 一个 问题。 但一开始就编写程序然后进行比较并不是好主意。 我们不想花费大量时间编写毫无价值的程序。 我们希望有一种方法来决定这项程序是否值得编写。 因此，我们大部分时间真正要做的是审视 算法 而不是程序，并使用 算法分析 来评估这些算法。
算法分析本质上是一项建模练习。 一个 模型 是对现实的简化，只保留基本要素。 有了模型，我们就能更容易地聚焦于并对这些要点进行推理。
本学期我们最主要的战术关注点将是如何识别一个算法是否高效。 为此我们需要（并且将会研究）大量的数学工具。 你的主要工具将是 求和 和 递推关系。 鉴于我们许多算法的性质，我们需要大量熟练使用对数。
3.1.1. 建模算法的代价¶
我们希望度量一个算法的代价。 我们希望这个过程尽可能简单。 我们需要一把尺子来定义算法的"代价"。 这把尺子的品质要求如下：
它应当度量我们关心的事物。 通常我们关心时间，但并非总是如此。
它应当是定量的，允许进行比较。
它应当易于计算（易于计算的是度量，而不是算法）。
它应当能够很好地预测相应程序的实际代价。
算法分析的基本驱动力是：随着问题规模的增大，算法的行为（增长 率）如何变化。 增添复杂性的是：算法在给定规模的不同输入上可能有不同的表现。 最好情况、平均情况和最坏情况的概念在这里登场。 要就算法的行为展开有意义的讨论，我们必须事先就 该算法在其输入规模增长时可能表现出的 哪一种 增长率为基准 达成一致。
要对一个算法的增长率建模，我们需要：
问题输入规模的度量。
求解工作量的度量。 * 我们用 基本操作 的计数作为求解工作量的度量。
要获得度量——无论是问题输入规模还是求解工作量——我们都必须有一个 代价模型。 与任何模型一样，它可能是也可能不是一个 好 模型。 这里有一个简单的例子。 假设我们的问题是计算一个值的平方。 我们把要平方的那个值当作输入规模。 （稍后我们会认识到，对于数值问题来说，这实际上是一种很糟糕的 建模输入规模的方式，但现在姑且这样。）
为给解的代价建模，我们假设对变量赋值需要固定的时间。 我们还假设所有其他操作都不花时间。 （这是不是一个好模型？无论好坏，它都 是 一个模型。）
算法 1:
sum = n*n;
发生了一次赋值，所以代价是 1。 对于这段代码片段代价的直觉看法，这是个好模型吗？ 多数人会觉得，对大多数目的而言，这是对所完成工作的合理估计。 所以它看起来是个合理的模型。
算法 2:
sum = 0;
for (i=1; i<=n; i++)
sum = sum + n;
所做的赋值次数是
现在，这里有很多可以吹毛求疵的地方。 取决于你如何处理循环变量， 你也许想说赋值次数是 \(2n + 1\)。 这造成了 \(n+1\) 与 \(2n+1\) 之间的差别。 这要紧吗？ 不太要紧。 我们一开始本来就不清楚一次操作的确切时间，所以 2 这个因子 似乎关系不大。 重要的是这两者的增长率相同， 无论加法与赋值的相对代价如何。 事实上，这才是关键考量。 也许我们担心一次赋值与一次乘法在真实运行时间上是否相同， 而乘法又可能与加法不同。 （在某些情况下，乘法与加法的代价不同确实是个合理的假设。） 也许递增循环变量与普通赋值的代价不同。 但与下面这一根本性认识相比，这些都无关紧要：本算法的代价 正比于输入规模（本例中是输入变量的值）。 \(n+1\) 和 \(2n+1\) 具有相同的线性增长率， 所以它们对算法增长率的预测同样有效。 如果我们都同意这种平方一个数的方法具有关于该数值大小的 线性增长率，那么就可以得出结论：以估算增长率为目的， 这是一个合理的模型。
算法 3:
sum = 0;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
sum = sum + 1;
所做的赋值次数是：
同样，对于这个算法的代价而言，这是个合理的模型。
现在，给定三个算法，并且我们已掌握度量其代价的模型，接下来的问题是： 这三个算法中哪一个最优（也就是说，运行所需的工作量最少）？ 显然，在这个意义上我们认为第一个是最优的。
与上述例子对比，考虑一个涉及字符串赋值的问题（通过拷贝字符串中的 字符来完成）。 在这种情况下，赋值具有常数时间代价的模型仍然有效吗？ 想一想。
作为建模的另一个例子： 考虑一个对线性表进行运算的问题，其中一项重要的基本 操作是访问线性表上的第 \(i\mathrm{th}\) 条记录。 我们可以取这样的模型：这样一次访问需要一单位工作。 如果该线性表用内存中的数组实现，那么我们大概会认为这是一个 "合理"的模型。 如果该线性表用单链表实现，那么我们大概 不会 认为这是一个 "合理"的模型。 （为什么？）
3.1.2. 大问题¶
我们如何创造高效的算法？ 我们使用问题求解和算法设计技能。 本学期我们将看到一些标准的算法设计技术。 其中一种对很多问题行之有效的设计技术的好例子是 动态规划。
我们如何识别一个"好"算法？ 这是一个关键问题，因为除非我们能识别出"好"算法， 否则我们不知道是否该停止寻找好算法。 我们的答案是：通过它的性能与问题内在难度之间的关系来判断。 当然，这需要一个度量算法性能的方法，以及一个度量问题内在 难度的方法。
一个问题有多"难"？ 也就是说，它的内在难度是什么？ 这就是问题 下界 概念发挥作用的地方。 目前，我们将"难"这个词限定为"运行起来要花多少钱？"。 稍后，我们将讨论"难"的另外一些不同含义。
本学期我们在处理一系列问题时，将遵循以下总体方案：
定义一个问题（PROBLEM）。
建立一个度量输入规模和问题求解代价的模型（MODEL）。
设计求解该问题的算法（ALGORITHM）。
- 在该模型下分析问题与算法（ANALYZE）。
分析算法以获得上界（UPPER BOUND）。
分析问题以获得下界（LOWER BOUND）。
比较两者，看看我们的解是否"足够好"（COMPARE）。
如果我们计算的两个界并不吻合，那么还有以下一些选项：
重新设计算法，或者发明一个新算法。
收紧界（如果它们还不够紧的话）。
改变模型。
改变问题。
3.2. 致谢¶
本页深受 Gregory J.E. Rawlins 所著 Compared to What? 中 第 1 章引言的阐述影响。
