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