17
时间复杂度
即使一个问题原则上是可判定的，因此在计算上是可解决的，但如果其解决方案需要过多的时间或内存，那么在实践中可能无法解决。在本书的最后一部分，我们介绍了计算复杂度理论——对解决计算问题所需的时间、内存或其他资源的研究。我们从时间开始。
本章的目的是介绍时间复杂度理论的基础知识。首先，我们介绍一种衡量解决问题所需时间的方法。然后，我们展示如何根据所需时间量对问题进行分类。之后，我们讨论某些可判定问题可能需要大量时间的可能性，以及如何确定何时面临此类问题。
7.1
衡量复杂度
我们从一个例子开始。考虑语言 $A=\left\{0^{k} 1^{k} \mid k \geq 0\right\}$。显然，$A$ 是一种可判定语言。一个单带图灵机需要多少时间来判定 $A$？我们检查下面用于 $A$ 的单带 TM $M_{1}$。我们给出
图灵机的低级别描述，包括磁带上的实际磁头移动，以便我们可以计算 $M_{1}$ 运行时使用的步数。
$M_{1}=$“在输入字符串 $w$ 上：
- 扫描磁带，如果发现 0 在 1 的右侧，则拒绝。
- 如果磁带上仍有 0 和 1，则重复：
- 扫描磁带，划掉一个 0 和一个 1。
- 如果划掉所有 1 后仍有 0 留下，或者划掉所有 0 后仍有 1 留下，则拒绝。否则，如果磁带上既没有 0 也没有 1，则接受。”
我们将分析 TM $M_{1}$ 判定 $A$ 的算法，以确定它使用了多少时间。首先，我们为此目的引入一些术语和符号。
算法在特定输入上使用的步数可能取决于几个参数。例如，如果输入是图，步数可能取决于节点数、边数、图的最大度，或者这些因素和/或其他因素的某种组合。为简单起见，我们仅将算法的运行时间计算为表示输入字符串长度的函数，而不考虑任何其他参数。在最坏情况分析中，我们在此考虑的形式，我们考虑特定长度所有输入中最长的运行时间。在平均情况分析中，我们考虑特定长度所有输入运行时间的平均值。
定义 7.1
令 $M$ 是一个在所有输入上都停机的确定性图灵机。$M$ 的运行时间或时间复杂度是函数 $f: \mathcal{N} \longrightarrow \mathcal{N}$，其中 $f(n)$ 是 $M$ 在任何长度为 $n$ 的输入上使用的最大步数。如果 $f(n)$ 是 $M$ 的运行时间，我们说 $M$ 在 $f(n)$ 时间内运行，并且 $M$ 是一个 $f(n)$ 时间的图灵机。习惯上我们用 $n$ 来表示输入的长度。
大O和小o记法
因为算法的精确运行时间通常是一个复杂的表达式，所以我们通常只对其进行估计。在一种方便的估计形式中，称为渐近分析，我们试图理解算法在大型输入上运行时所需的运行时间。我们通过只考虑算法运行时间表达式的最高阶项来实现这一点，忽略该项的系数和任何低阶项，因为最高阶项在大型输入上支配其他项。
例如，函数 $f(n)=6 n^{3}+2 n^{2}+20 n+45$ 有四项，最高阶项是 $6 n^{3}$。忽略系数 6，我们说 $f$ 渐近地至多为 $n^{3}$。描述这种关系的渐近记法或大O记法是 $f(n)=O\left(n^{3}\right)$。我们在以下定义中形式化这一概念。令 $\mathcal{R}^{+}$为非负实数集。
定义 7.2
令 $f$ 和 $g$ 是函数 $f, g: \mathcal{N} \longrightarrow \mathcal{R}^{+}$。我们说 $\boldsymbol{f}(\boldsymbol{n})=\boldsymbol{O}(\boldsymbol{g}(\boldsymbol{n}))$，如果存在正整数 $c$ 和 $n_{0}$，使得对于每个整数 $n \geq n_{0}$，
当 $f(n)=O(g(n))$ 时，我们说 $g(n)$ 是 $f(n)$ 的上界，或者更精确地说，$g(n)$ 是 $f(n)$ 的渐近上界，以强调我们忽略了常数因子。
直观地，$f(n)=O(g(n))$ 意味着如果我们忽略常数因子差异，则 $f$ 小于或等于 $g$。您可以将 $O$ 视为表示一个被忽略的常数。在实践中，您可能会遇到的绝大多数函数 $f$ 都有一个明显的最高阶项 $h$。在这种情况下，写成 $f(n)=O(g(n))$，其中 $g$ 是 $h$ 去掉其系数后的结果。
示例 7.3
令 $f_{1}(n)$ 是函数 $5 n^{3}+2 n^{2}+22 n+6$。那么，选择最高阶项 $5 n^{3}$ 并忽略其系数 5 得到 $f_{1}(n)=O\left(n^{3}\right)$。
我们来验证这个结果是否满足形式定义。我们通过令 $c$ 为 6 且 $n_{0}$ 为 10 来实现。那么，对于每个 $n \geq 10$，有 $5 n^{3}+2 n^{2}+22 n+6 \leq 6 n^{3}$。
此外，$f_{1}(n)=O\left(n^{4}\right)$，因为 $n^{4}$ 大于 $n^{3}$，因此仍然是 $f_{1}$ 的渐近上界。
然而，$f_{1}(n)$ 不是 $O\left(n^{2}\right)$。无论我们给 $c$ 和 $n_{0}$ 赋什么值，在这种情况下定义仍然不满足。
示例 7.4
大-$O$ 与对数以一种特殊的方式相互作用。通常当我们使用对数时，我们必须指定底数，如 $x=\log _{2} n$。这里的底数 2 表示这个等式等价于 $2^{x}=n$。改变底数 $b$ 的值会使 $\log _{b} n$ 的值改变一个常数因子，这归因于恒等式 $\log _{b} n=\log _{2} n / \log _{2} b$。因此，当我们写 $f(n)=O(\log n)$ 时，不再需要指定底数，因为我们反正都在忽略常数因子。
令 $f_{2}(n)$ 是函数 $3 n \log _{2} n+5 n \log _{2} \log _{2} n+2$。在这种情况下，我们有 $f_{2}(n)=O(n \log n)$，因为 $\log n$ 支配 $\log \log n$。
大-$O$ 记法也出现在算术表达式中，例如表达式 $f(n)=O\left(n^{2}\right)+O(n)$。在这种情况下，每个 $O$ 符号的出现代表一个不同的被抑制的常数。由于 $O\left(n^{2}\right)$ 项支配 $O(n)$ 项，所以该表达式等价于 $f(n)=O\left(n^{2}\right)$。当 $O$ 符号出现在指数中时，如表达式 $f(n)=2^{O(n)}$，同样的思想适用。该表达式表示对于某个常数 $c$，存在一个 $2^{c n}$ 的上界。
表达式 $f(n)=2^{O(\log n)}$ 出现在某些分析中。使用恒等式 $n=2^{\log _{2} n}$，因此 $n^{c}=2^{c \log _{2} n}$，我们看到 $2^{O(\log n)}$ 表示对于某个 $c$，存在一个 $n^{c}$ 的上界。表达式 $n^{O(1)}$ 以另一种方式表示相同的界，因为表达式 $O(1)$ 表示一个值，它从不超过一个固定的常数。
我们经常导出形如 $n^{c}$（其中 $c$ 大于 0）的界。这样的界称为多项式界。形如 $2^{\left(n^{\delta}\right)}$（其中 $\delta$ 是大于 0 的实数）的界称为指数界。
大-$O$ 记法有一个伴随称为小o记法。大-$O$ 记法表示一个函数渐近地不超过另一个函数。要表示一个函数渐近地小于另一个函数，我们使用小o记法。大-$O$ 和小o记法之间的区别类似于 $\leq$ 和 $<$ 之间的区别。
定义 7.5
令 $f$ 和 $g$ 是函数 $f, g: \mathcal{N} \longrightarrow \mathcal{R}^{+}$。如果
我们说 $\boldsymbol{f}(\boldsymbol{n})=\boldsymbol{o}(\boldsymbol{g}(\boldsymbol{n}))$。
换句话说，$f(n)=o(g(n))$ 意味着对于任何实数 $c>0$，存在一个数 $n_{0}$，使得对于所有 $n \geq n_{0}$，有 $f(n)<c g(n)$。
示例 7.6
以下内容很容易验证。
- $\sqrt{n}=o(n)$。
- $n=o(n \log \log n)$。
- $n \log \log n=o(n \log n)$。
- $n \log n=o\left(n^{2}\right)$。
- $n^{2}=o\left(n^{3}\right)$。
然而，$f(n)$ 从来不是 $o(f(n))$。$\square$
算法分析
我们来分析为语言 $A=\left\{0^{k} 1^{k} \mid k \geq 0\right\}$ 给出的 TM 算法。为方便起见，我们在此重复该算法。
$M_{1}=$“在输入字符串 $w$ 上：
- 扫描磁带，如果发现 0 在 1 的右侧，则拒绝。
- 如果磁带上仍有 0 和 1，则重复：
- 扫描磁带，划掉一个 0 和一个 1。
- 如果划掉所有 1 后仍有 0 留下，或者划掉所有 0 后仍有 1 留下，则拒绝。否则，如果磁带上既没有 0 也没有 1，则接受。”
为了分析 $M_{1}$，我们分别考虑其四个阶段。在阶段 1 中，机器扫描磁带以验证输入是否为 $0^{*} 1^{*}$ 的形式。执行此扫描需要 $n$ 步。如前所述，我们通常用 $n$ 来表示输入的长度。将磁头重新定位到磁带左端需要另外 $n$ 步。因此，此阶段总共使用了 $2n$ 步。在大-$O$ 记法中，我们说此阶段使用了 $O(n)$ 步。请注意，我们没有在机器描述中提及磁头重新定位。使用渐近记法允许我们省略机器描述中最多影响运行时间一个常数因子的细节。
在阶段 2 和 3 中，机器反复扫描磁带，并在每次扫描中划掉一个 0 和一个 1。每次扫描使用 $O(n)$ 步。因为每次扫描划掉两个符号，所以最多可以发生 $n/2$ 次扫描。因此，阶段 2 和 3 所花费的总时间是 $(n/2)O(n) = O(n^2)$ 步。
在阶段 4 中，机器进行一次扫描以决定接受或拒绝。此阶段花费的时间最多为 $O(n)$。
因此，$M_{1}$ 在长度为 $n$ 的输入上的总时间是 $O(n)+O\left(n^{2}\right)+O(n)$，即 $O\left(n^{2}\right)$。换句话说，它的运行时间是 $O\left(n^{2}\right)$，这完成了对该机器的时间分析。
让我们为根据语言的时间要求对其进行分类设置一些符号。
定义 7.7
令 $t: \mathcal{N} \longrightarrow \mathcal{R}^{+}$是一个函数。定义时间复杂度类 TIME($\boldsymbol{t}(\boldsymbol{n})$) 为所有可由 $O(t(n))$ 时间图灵机判定的语言的集合。
回想语言 $A=\left\{0^{k} 1^{k} \mid k \geq 0\right\}$。前面的分析表明 $A \in \operatorname{TIME}\left(n^{2}\right)$，因为 $M_{1}$ 在 $O\left(n^{2}\right)$ 时间内判定 $A$，并且 $\operatorname{TIME}\left(n^{2}\right)$ 包含所有可以在 $O\left(n^{2}\right)$ 时间内判定的语言。
是否存在一台机器可以渐近地更快地判定 $A$？换句话说，$A$ 是否在 $t(n)=o\left(n^{2}\right)$ 的 $\operatorname{TIME}(t(n))$ 中？我们可以通过在每次扫描中划掉两个 0 和两个 1 来改进运行时间，而不是只划掉一个，因为这样做可以将扫描次数减少一半。但这只会将运行时间改进 2 倍，并且不影响渐近运行时间。以下机器 $M_{2}$ 使用不同的方法来渐近地更快地判定 $A$。它表明 $A \in \operatorname{TIME}(n \log n)$。
$M_{2}=$“在输入字符串 $w$ 上：
- 扫描磁带，如果发现 0 在 1 的右侧，则拒绝。
- 只要磁带上仍有一些 0 和一些 1，就重复：
- 扫描磁带，检查剩余的 0 和 1 的总数是偶数还是奇数。如果是奇数，则拒绝。
- 再次扫描磁带，从第一个 0 开始划掉每隔一个 0，然后从第一个 1 开始划掉每隔一个 1。
- 如果磁带上没有 0 也没有 1 留下，则接受。否则，拒绝。”
在分析 $M_{2}$ 之前，我们先验证它确实判定 $A$。在阶段 4 中执行的每次扫描中，剩余 0 的总数减半，任何余数都被丢弃。因此，如果我们从 13 个 0 开始，在阶段 4 执行一次后，只剩下 6 个 0。在随后的执行中，剩下 3 个，然后 1 个，然后 0 个。此阶段对 1 的数量具有相同的影响。
现在我们检查阶段 3 每次执行时 0 的数量和 1 的数量的偶/奇奇偶性。再次考虑从 13 个 0 和 13 个 1 开始。阶段 3 的第一次执行发现奇数个 0（因为 13 是奇数）和奇数个 1。在随后的执行中，出现偶数个（6），然后奇数个（3），然后奇数个（1）。我们不会对 0 个 0 或 0 个 1 执行此阶段，因为阶段 2 中指定的重复循环条件。对于发现的奇偶性序列（奇数、偶数、奇数、奇数），如果我们将偶数替换为 0，奇数替换为 1，然后反转序列，我们得到 1101，即 13 的二进制表示，或者说是开始时 0 和 1 的数量。奇偶性序列总是给出二进制表示的反转。
当阶段 3 检查以确定剩余的 0 和 1 的总数是偶数时，它实际上是在检查 0 的奇偶性与 1 的奇偶性是否一致。如果所有奇偶性都一致，则 0 的数量和 1 的数量的二进制表示一致，因此这两个数字相等。
为了分析 $M_{2}$ 的运行时间，我们首先观察到每个阶段都需要 $O(n)$ 时间。然后我们确定每个阶段执行的次数。阶段 1 和 5 各执行一次，总共花费 $O(n)$ 时间。阶段 4 每次执行时至少划掉一半的 0 和 1，因此在所有都划掉之前，重复循环最多执行 $1+\log _{2} n$ 次迭代。因此，阶段 2、3 和 4 的总时间是 $(1+\log _{2} n) O(n)$，即 $O(n \log n)$。$M_{2}$ 的运行时间是 $O(n)+O(n \log n)=O(n \log n)$。
早些时候我们表明 $A \in \operatorname{TIME}\left(n^{2}\right)$，但现在我们有一个更好的界——即 $A \in \operatorname{TIME}(n \log n)$。这个结果在单带图灵机上无法进一步改进。事实上，任何可以在单带图灵机上在 $o(n \log n)$ 时间内判定的语言都是正则语言，如问题 7.20 要求您展示的那样。
如果图灵机有第二个磁带，我们可以在 $O(n)$ 时间（也称为线性时间）内判定语言 $A$。以下两带 TM $M_{3}$ 在线性时间内判定 $A$。机器 $M_{3}$ 的操作方式与之前用于 $A$ 的机器不同。它只是将 0 复制到其第二个磁带，然后将它们与 1 进行匹配。
$M_{3}=$“在输入字符串 $w$ 上：
- 扫描磁带 1，如果发现 0 在 1 的右侧，则拒绝。
- 扫描磁带 1 上的 0，直到第一个 1。同时，将 0 复制到磁带 2。
- 扫描磁带 1 上的 1，直到输入结束。对于在磁带 1 上读取的每个 1，划掉磁带 2 上的一个 0。如果在读取所有 1 之前所有 0 都已划掉，则拒绝。
- 如果所有 0 都已划掉，则接受。如果仍有 0 留下，则拒绝。”
这台机器很容易分析。四个阶段中的每个阶段都使用 $O(n)$ 步，因此总运行时间是 $O(n)$，因此是线性的。请注意，这个运行时间是最好的，因为仅仅读取输入就需要 $n$ 步。
让我们总结一下我们关于 $A$ 的时间复杂度，即判定 $A$ 所需的时间量所展示的内容。我们生产了一台单带 TM $M_{1}$，它在 $O\left(n^{2}\right)$ 时间内判定 $A$，以及一台更快的单带 TM $M_{2}$，它在 $O(n \log n)$ 时间内判定 $A$。问题 7.20 的解决方案意味着没有单带 TM 可以更快地完成。然后我们展示了一台两带 TM $M_{3}$，它在 $O(n)$ 时间内判定 $A$。因此，在单带 TM 上 $A$ 的时间复杂度是 $O(n \log n)$，在两带 TM 上是 $O(n)$。请注意，$A$ 的复杂度取决于所选择的计算模型。
这一讨论强调了复杂度理论与可计算性理论之间的重要区别。在可计算性理论中，丘奇-图灵论题意味着所有合理的计算模型都是等价的——也就是说，它们都判定相同类别的语言。在复杂度理论中，模型的选择会影响语言的时间复杂度。例如，在一个模型上可在线性时间内判定的语言，在另一个模型上不一定能在线性时间内判定。
在复杂度理论中，我们根据计算问题的时间复杂度对其进行分类。但是我们用哪种模型来衡量时间呢？相同的语言在不同的模型上可能有不同的时间要求。
幸运的是，对于典型的确定性模型，时间要求差异不大。因此，如果我们的分类系统对复杂度相对较小的差异不那么敏感，那么确定性模型的选择并不关键。我们将在接下来的几节中进一步讨论这个想法。
模型之间的复杂度关系
在这里，我们研究计算模型的选择如何影响语言的时间复杂度。我们考虑三种模型：单带图灵机；多带图灵机；以及非确定性图灵机。
定理 7.8
令 $t(n)$ 是一个函数，其中 $t(n) \geq n$。那么，每个 $t(n)$ 时间的多带图灵机都有一台等价的 $O\left(t^{2}(n)\right)$ 时间的单带图灵机。
证明思路 该定理的证明思想非常简单。回想在定理 3.13 中，我们展示了如何将任何多带 TM 转换为模拟它的单带 TM。现在我们分析该模拟以确定它需要多少额外时间。我们证明模拟多带机器的每一步在单带机器上最多使用 $O(t(n))$ 步。因此，使用的总时间是 $O\left(t^{2}(n)\right)$ 步。
证明 令 $M$ 是一台在 $t(n)$ 时间内运行的 $k$ 带 TM。我们构造一台在 $O\left(t^{2}(n)\right)$ 时间内运行的单带 TM $S$。
机器 $S$ 通过模拟 $M$ 来操作，如定理 3.13 中所述。为了回顾该模拟，我们回想 $S$ 使用其单带表示 $M$ 的所有 $k$ 个磁带上的内容。磁带连续存储，其中 $M$ 的磁头位置标记在相应的方格上。
最初，$S$ 将其磁带格式化为表示 $M$ 所有磁带的格式，然后模拟 $M$ 的步骤。为了模拟一步，$S$ 扫描其磁带上存储的所有信息，以确定 $M$ 磁头下的符号。然后 $S$ 再次扫描其磁带，以更新磁带内容和磁头位置。如果 $M$ 的一个磁头向右移动到其磁带上以前未读取的部分，则 $S$ 必须增加分配给该磁带的空间量。它通过将其自身磁带的一部分向右移动一个单元格来实现。
现在我们分析这个模拟。对于 $M$ 的每一步，机器 $S$ 对其活动部分进行两次扫描。第一次获得确定下一步行动所需的信息，第二次执行该行动。$S$ 磁带活动部分的长度决定了 $S$ 扫描它所需的时间，所以我们必须确定这个长度的上限。为此，我们取 $M$ 的 $k$ 个磁带活动部分长度的总和。每个活动部分的长度最多为 $t(n)$，因为如果磁头每一步都向右移动，$M$ 在 $t(n)$ 步中使用了 $t(n)$ 个磁带单元格，如果磁头曾向左移动，则更少。因此，扫描 $S$ 磁带的活动部分使用 $O(t(n))$ 步。
为了模拟 $M$ 的每一步，$S$ 执行两次扫描，并且可能多达 $k$ 次向右移动。每次使用 $O(t(n))$ 时间，因此 $S$ 模拟 $M$ 的一步所需总时间是 $O(t(n))$。
现在我们限定模拟所用的总时间。初始阶段，$S$ 将其磁带格式化为正确的格式，使用 $O(n)$ 步。之后，$S$ 模拟 $M$ 的 $t(n)$ 步，每步使用 $O(t(n))$ 步，因此模拟的这一部分
使用 $t(n) \times O(t(n))=O\left(t^{2}(n)\right)$ 步。因此，$M$ 的整个模拟使用了 $O(n)+O\left(t^{2}(n)\right)$ 步。
我们假设 $t(n) \geq n$（一个合理的假设，因为 $M$ 甚至无法在更短的时间内读取整个输入）。因此，$S$ 的运行时间是 $O\left(t^{2}(n)\right)$，证明完成。
接下来，我们考虑非确定性单带图灵机的类似定理。我们证明，任何在此类机器上可判定的语言，都可以在确定性单带图灵机上判定，但需要显著更多的时间。在此之前，我们必须定义非确定性图灵机的运行时间。回想非确定性图灵机是判定机，如果它的所有计算分支都在所有输入上停机。
定义 7.9
令 $N$ 是一个非确定性图灵机，它是一个判定机。$N$ 的运行时间是函数 $f: \mathcal{N} \longrightarrow \mathcal{N}$，其中 $f(n)$ 是 $N$ 在任何长度为 $n$ 的输入上的任何计算分支中使用的最大步数，如下图所示。
图 7.10
衡量确定性和非确定性时间
非确定性图灵机的运行时间定义并非旨在与任何实际世界的计算设备相对应。相反，它是一个有用的数学定义，有助于表征一类重要计算问题的复杂度，我们将在稍后演示。
定理 7.11
令 $t(n)$ 是一个函数，其中 $t(n) \geq n$。那么，每个 $t(n)$ 时间的非确定性单带图灵机都有一台等价的 $2^{O(t(n))}$ 时间的确定性单带图灵机。
证明 令 $N$ 是一台在 $t(n)$ 时间内运行的非确定性 TM。我们构造一台确定性 TM $D$，它通过搜索 $N$ 的非确定性计算树来模拟 $N$，如定理 3.16 的证明中所述。现在我们分析该模拟。
在长度为 $n$ 的输入上，$N$ 的非确定性计算树的每个分支的长度最多为 $t(n)$。树中的每个节点最多可以有 $b$ 个子节点，其中 $b$ 是 $N$ 的转移函数给出的合法选择的最大数量。因此，树中叶子的总数最多为 $b^{t(n)}$。
模拟通过广度优先探索这棵树进行。换句话说，它在处理深度 $d+1$ 的任何节点之前，会访问深度 $d$ 的所有节点。定理 3.16 证明中给出的算法在每次访问节点时都从根开始并向下遍历到该节点，效率低下。但消除这种低效率并不会改变当前定理的陈述，所以我们保留它。树中节点的总数小于最大叶子数的两倍，所以我们将其限制为 $O\left(b^{t(n)}\right)$。从根开始并向下遍历到节点所需的时间是 $O(t(n))$。因此，$D$ 的运行时间是 $O\left(t(n) b^{t(n)}\right)=2^{O(t(n))}$。
如定理 3.16 所述，TM $D$ 有三个磁带。根据定理 7.8，转换为单带 TM 最多会将运行时间平方。因此，单带模拟器的运行时间是 $\left(2^{O(t(n))}\right)^{2}=2^{O(2 t(n))}=2^{O(t(n))}$，定理得证。