2. 界回顾¶
2.1. 界回顾¶
我们为一个问题（在某些情况下：最坏情况、平均情况或最佳情况）定义 upper bound 为我们所知最好的算法的上界（在那个情况下！），而 下界 则为我们能够证明的所有算法中最低的下界（在那个情况下！）。虽然我们通常可以识别出给定算法的上界，但找到所有可能的算法中最低的下界通常很困难，特别是如果该下界大于由测量必须处理的输入量确定的“琐碎”下界。
能够发现一个强下界的好处是显著的。 特别是，当我们能让一个问题的上下界会合时， 就意味着我们在理论意义上真正理解了我们的问题。 它还省去了我们试图发现更多（渐近意义上）高效算法的 努力——因为这样的算法不可能存在。
通常，确定一个问题下界最有效的途径是找出一个以已知下界 的另一个问题的 归约 。 但是，当我们找不到合适的"相似问题"时，这种方法帮不上忙。 我们将重点关注的一件事是，从基本原理出发 发现并证明下界。 你大概见过的最重要的下界论证例子是 排序下界证明 ， 它表明排序问题在 最坏情况 下有一个 \(\Omega(n \log n)\) 的下界。
问题的下界指的是任何算法 必须 做的工作量。 它是我们能对 所有可能求解该问题的算法 证明的最紧（最高）下界。 这可能是一道难题，因为我们不可能知道一个问题的所有算法—— 理论上算法有无限多个。 不过，我们常常可以从一个基于必须检查的输入量的 简单下界入手。 例如，我们可以论证，任何在无序线性表中找最大元素的算法 的下界必定是 \(\Omega(n)\)，因为任何算法都必须检查所有输入， 才能确定它确实找到了最大值。
就找最大值而言，我们已知的、以 \(O(n)\) 时间运行的 简单算法这一事实，加上任何算法都需要 \(\Omega(n)\) 时间 这一事实，是很有意义的。 因为我们的上下界会合了（在常数因子内）， 我们知道我们确实有一个求解该问题的"好"算法。 有人可能开发出一个比现有实现"稍快"的实现，只是相差一个常数因子。 例如，取决于算法具体怎么写， 比较次数可能多一次或少一次。 但因为算法的上界与问题的下界会合，我们知道不可能开发出一个 渐近意义上更好的算法。
但是，我们必须小心如何解读这最后一句话。 就算当时已经有归并排序，快速排序的发明无疑还是让世界变得更美好。 快速排序在渐近意义上并不比归并排序快，但它也不仅仅是 归并排序的"调优"。 快速排序是一种实质不同的排序方法。 所以即使某个问题的上下界相合， 一个新颖巧妙的算法仍能带来好处。
2.1.1. 分析问题¶
我们分析问题的第一个例子是汉诺塔。 它的好处是：对于给定的输入规模 \(n\)， 它只有一个输入（值 \(n\)）。 当然，这并不总是成立的。 例如，对于在 \(n\) 条记录的数组中找最大值的问题， 有很多种思考其输入的方式。 我们可以考虑包含 \(n\) 个任意值的数组， 其中（理论上）存在无限多个规模为 \(n\) 的输入。 如果我们连全部可能的输入都无法枚举，那可能就难以理解 某类问题的分析。 所以我们也许更愿意采用一个我们相信不会改变底层行为的 更简单的模型。 例如，我们可以假设输入是值 1 到 \(n\) 的某个排列。 虽然我们可能不想把找最大值的算法限制在这样的输入上， 但如果我们做分析时关心的只是最大值在数组中的位置， 那么值 1 到 \(n\) 的排列也许能让我们更容易 想清楚所有可能性。
另一个可能出现的复杂因素是：给定规模的不同输入 可能有不同的代价。 例如，我们大概都明白，要在数组中找最大值， 我们需要过一遍数组的所有值。 所以，值的顺序其实不影响所需时间。 但是，考虑我们的问题是找值 \(X\) 的记录在数组中的 位置（如果存在这样的记录）。 现在不仅存在许多规模为 \(n\) 的可能输入，而且 用例如从数组头部开始的简单顺序查找时，这些输入的 代价也不同。 这就是我们需要最好、平均和最坏情况输入概念的原因。
更糟的是，给定输入求解问题的代价取决于我们所用的算法！ 例如，对找出值 \(X\) 记录位置的问题，从数组头向尾 顺序移动的算法，与从数组尾向头 顺序移动的算法，其最坏的输入并不是同一个规模 \(n\) 的输入。
对于所有输入大小为 $n$ 的情况，算法的最大成本为 $ worst-case cost $（对于所有问题实例大小为 $ \(n\) $ 的情况）。对于所有问题实例大小为 $ \(n\) $ 的情况，算法的最小成本为 $ best-case cost $。有可能，{最佳、最坏} 情况的成本会随着 $ \(n\) $ 发生根本性变化。也就是说，即使是 $ \(n\) $ 也可能与奇数 $ \(n\) $ 具有截然不同的成本。
本学期我们在各种场合将使用以下记法。 \(\mathcal{A}\) 是一个算法。 \(I_n\) 是 \(\mathcal{A}\) 的所有规模为 \(n\) 的可能输入集合。 \(I\) 是 \(I_n\) 中的一个输入。 \(f_\mathcal{A}\) 是表示算法 \(\mathcal{A}\) 资源代价的 函数，其中 \(f_\mathcal{A}(I)\) 是对输入 \(I\) 使用 该算法的代价。 使用这一记法，我们可以把最坏和最好情况代价定义为：
我们是在考虑规模 \(n\) 的所有输入，这很关键。 换句话说，我们不能挑选出现最好（或最坏）情况的那个 \(n\)。 所以说"最好情况是 \(n=1\) 时"这样的话是错误的。
如果我们想要 平均情况代价， 那就更复杂了。 我们也许会把它建模为最好情况代价与最坏情况代价的中间值， 但这常常并不正确。 （想一想在什么情况下它是对的，以及一些它不对的情形。） 要体现规模为 \(n\) 的输入的真实平均代价， 我们必须考虑这一类输入的整体。 对其中每一个输入，我们需要它的相对频率和它的代价。 输入的频率往往很难确定！ 例如，顺序查找的平均代价是 \((n+1)/2\)， 但 只有 当数组每个位置含有所找值的概率相等时才成立。 而且，如果值根本不在数组中，我们又该怎么办？
不过，理想情况下我们拥有计算平均情况代价所需的 全部信息。 然后我们可以计算加权平均：
想一想：平均代价能比最坏代价差吗？ 或者比最好代价好？
所以现在我们准备给出问题下界更精确的定义。 和往常一样，我们必须把它对某一类输入来定义。 我们还必须考虑到有很多（理论上无限多）算法能求解这个问题。 回忆一下，要分析任何问题，我们都必须定义一个模型， 包括问题规模的定义和解代价的定义。 把这样的模型记作 \(\mathcal{M}\)。 那么，\(\mathcal{A_M}\) 就是模型 \(\mathcal{M}\) 下 求解该问题的所有算法的集合。 于是，一个问题在 最坏情况 下的下界是：
2.1.2. 对输入建模¶
尤其是当试图弄清算法的平均情况代价到底是什么时， 如果我们简化所考虑输入类别的模型， 可能会更容易想清楚发生了什么。
思考这个看似简单的问题：在（无序的）:math:n 条记录数组中 找值 \(X\)。 这个问题的输入是什么？ 当然，是包含 \(n\) 条记录的数组！ 但如果我们想枚举所有规模为 \(n\) 的输入，这意味着什么？ 这样的输入有多少个？
嗯，如果数组中的每个位置可以取任意值，那么每个位置 都有无限多个可能的值。 即使我们把这些值限制为类似 64 位整数， 要考虑的可能性仍然多得惊人！
考虑到思考所有这些输入所带来的认知负担， 我们可能宁愿改为分析一组更简单的输入。 例如，我们可以决定（出于分析目的）只考虑 输入是数字 1 到 \(n\) 的一个排列。 这里的论证可以是：我们不关心数组中的实际值。 我们只关心给定值是不是 \(X\)， 所以我们可以简化所考虑的输入。
进行这样的简化时，我们必须注意两个危险。 第一，我们的简化仍然必须反映现实。 如果我们把 \(n\) 个数字的数组简化为数字 1 到 \(n\) 的排列，那就排除了带重复的输入。 这可能导致错误的分析。 第二，我们必须把为了分析目的的输入问题与为了求解问题的 输入问题区分开。 就排序而言，我们可能想分析在一组 \(n\) 条记录（每条记录的 键值唯一）上的行为。 既然我们不关心实际的键值，我们也许能把它简化为 记录键值为 1 到 \(n\) 的某个排列。 但是，对已知键是值 1 到 \(n\) 的一个排列的记录集合排序， 要比对 \(n\) 条任意记录排序简单得多！ 例如，我们可以用简单的 Binsort 在线性时间内 对该排列排序。
回到在 \(n\) 条记录的数组中找值 \(X\) 的例子， 我们可能想考虑一个只关心 \(X\) 在数组中首次出现位置的模型。 换句话说，我们把所有 \(X\) 首次出现在第一个位置的输入 归并为一个输入。 所有 \(X\) 首次出现在第二个位置的输入是另一个输入。 依此类推。 然后我们只对那些我们关心的"组"输入分析代价。 当然，我们可能会在确定这些合成输入组合各自的频率时 遇到困难。 也许合理的是说数组中每个位置含 \(X\) 首次出现的 概率相等。 也许并不合理。
