计算理论

计算理论包括自动机理论与语言、可计算性理论、计算复杂性理论。

我们主要关注计算复杂性理论。

时空复杂度#

时间复杂度和空间复杂度是衡量一个算法效率的重要标准．

基本操作数#

同一个算法在不同的计算机上运行的速度会有一定的差别，并且实际运行速度难以在理论上进行计算，实际去测量又比较麻烦，所以我们通常考虑的不是算法运行的实际用时，而是算法运行所需要进行的基本操作的数量．

在普通的计算机上，加减乘除、访问变量（基本数据类型的变量，下同）、给变量赋值等都可以看作基本操作．

对基本操作的计数或是估测可以作为评判算法用时的指标．

时间复杂度#

定义#

衡量一个算法的快慢，一定要考虑数据规模的大小．所谓数据规模，一般指输入的数字个数、输入中给出的图的点数与边数等等．一般来说，数据规模越大，算法的用时就越长．而在算法竞赛中，我们衡量一个算法的效率时，最重要的不是看它在某个数据规模下的用时，而是看它的用时随数据规模而增长的趋势，即 时间复杂度．

引入#

考虑用时随数据规模变化的趋势的主要原因有以下几点：

现代计算机每秒可以处理数亿乃至更多次基本运算，因此我们处理的数据规模通常很大．如果算法 A 在规模为 $n$ 的数据上用时为 $100n$ 而算法 B 在规模为 $n$ 的数据上用时为 $n^2$ ，在数据规模小于 $100$ 时算法 B 用时更短，但在一秒钟内算法 A 可以处理数百万规模的数据，而算法 B 只能处理数万规模的数据．在允许算法执行时间更久时，时间复杂度对可处理数据规模的影响就会更加明显，远大于同一数据规模下用时的影响．
我们采用基本操作数来表示算法的用时，而不同的基本操作实际用时是不同的，例如加减法的用时远小于除法的用时．计算时间复杂度而忽略不同基本操作之间的区别以及一次基本操作与十次基本操作之间的区别，可以消除基本操作间用时不同的影响．

当然，算法的运行用时并非完全由输入规模决定，而是也与输入的内容相关．所以，时间复杂度又分为几种，例如：

最坏时间复杂度，即每个输入规模下用时最长的输入对应的时间复杂度．在算法竞赛中，由于输入可以在给定的数据范围内任意给定，我们为保证算法能够通过某个数据范围内的任何数据，一般考虑最坏时间复杂度．
平均（期望）时间复杂度，即每个输入规模下所有可能输入对应用时的平均值的复杂度（随机输入下期望用时的复杂度）．

所谓「用时随数据规模而增长的趋势」是一个模糊的概念，我们需要借助下文所介绍的 渐近符号 来形式化地表示时间复杂度．

渐近符号的定义#

渐近符号是函数的阶的规范描述．简单来说，渐近符号忽略了一个函数中增长较慢的部分以及各项的系数（在时间复杂度相关分析中，系数一般被称作「常数」），而保留了可以用来表明该函数增长趋势的重要部分．

一个简单的记忆方法是，含等于（非严格）用大写，不含等于（严格）用小写，相等是 $\Theta$ ，小于是 $O$ ，大于是 $\Omega$ ．大 $O$ 和小 $o$ 原本是希腊字母 Omicron，由于字形相同，也可以理解为拉丁字母的大 $O$ 和小 $o$ ．

在英文中，词根「-micro-」和「-mega-」常用于表示 10 的负六次方（百万分之一）和六次方（百万），也表示「小」和「大」．小和大也是希腊字母 Omicron 和 Omega 常表示的含义．

大 $\Theta$ 符号#

对于函数 $f(n)$ 和 $g(n)$ ， $f(n)=\Theta(g(n))$ ，当且仅当 $\exists c_1,c_2,n_0>0$ ，使得 $\forall n \ge n_0, 0\le c_1\cdot g(n)\le f(n) \le c_2\cdot g(n)$ ．

也就是说，如果函数 $f(n)=\Theta(g(n))$ ，那么我们能找到两个正数 $c_1, c_2$ 使得 $f(n)$ 被 $c_1\cdot g(n)$ 和 $c_2\cdot g(n)$ 夹在中间．

例如， $3n^2+5n-3=\Theta(n^2)$ , 这里的 $c_1, c_2, n_0$ 可以分别是 $2, 4, 100$ ． $n\sqrt {n} + n{\log^5 n} + m{\log m} +nm=\Theta(n\sqrt {n} + m{\log m} + nm)$ ，这里的 $c_1, c_2, n_0$ 可以分别是 $1, 2, 100$ ．

大 $O$ 符号#

$\Theta$ 符号同时给了我们一个函数的上下界，如果只知道一个函数的渐近上界而不知道其渐近下界，可以使用 $O$ 符号． $f(n)=O(g(n))$ ，当且仅当 $\exists c,n_0$ ，使得 $\forall n \ge n_0,0\le f(n)\le c\cdot g(n)$ ．

研究时间复杂度时通常会使用 $O$ 符号，因为我们关注的通常是程序用时的上界，而不关心其用时的下界．

需要注意的是，这里的「上界」和「下界」是对于函数的变化趋势而言的，而不是对算法而言的．算法用时的上界对应的是「最坏时间复杂度」而非大 $O$ 记号．所以，使用 $\Theta$ 记号表示最坏时间复杂度是完全可行的，甚至可以说 $\Theta$ 比 $O$ 更加精确，而使用 $O$ 记号的主要原因，一是我们有时只能证明时间复杂度的上界而无法证明其下界（这种情况一般出现在较为复杂的算法以及复杂度分析），二是 $O$ 在电脑上输入更方便一些．

大 $\Omega$ 符号#

同样的，我们使用 $\Omega$ 符号来描述一个函数的渐近下界． $f(n)=\Omega(g(n))$ ，当且仅当 $\exists c,n_0$ ，使得 $\forall n \ge n_0,0\le c\cdot g(n)\le f(n)$ ．

小 $o$ 符号#

如果说 $O$ 符号相当于小于等于号，那么 $o$ 符号就相当于小于号．

小 $o$ 符号大量应用于数学分析中，函数在某点处的泰勒展开式拥有皮亚诺余项，使用小 $o$ 符号表示严格小于，从而进行等价无穷小的渐近分析．

$f(n)=o(g(n))$ ，当且仅当对于任意给定的正数 $c$ ， $\exists n_0$ ，使得 $\forall n \ge n_0,0\le f(n)< c\cdot g(n)$ ．

小 $\omega$ 符号#

如果说 $\Omega$ 符号相当于大于等于号，那么 $\omega$ 符号就相当于大于号．

$f(n)=\omega(g(n))$ ，当且仅当对于任意给定的正数 $c$ ， $\exists n_0$ ，使得 $\forall n \ge n_0,0\le c\cdot g(n)< f(n)$ ．

常见性质#

$f(n) = \Theta(g(n))\iff f(n)=O(g(n))\land f(n)=\Omega(g(n))$
$f_1(n) + f_2(n) = O(\max(f_1(n), f_2(n)))$
$f_1(n) \times f_2(n) = O(f_1(n) \times f_2(n))$
$\forall a \neq 1, \log_a{n} = O(\log_2 n)$ ．由换底公式可以得知，任何对数函数无论底数为何，都具有相同的增长率，因此渐近时间复杂度中对数的底数一般省略不写．

简单的时间复杂度计算的例子#

int n, m;
std::cin >> n >> m;
for (int i = 0; i < n; ++i) {
  for (int j = 0; j < n; ++j) {
	for (int k = 0; k < m; ++k) {
	  std::cout << "hello world\n";
	}
  }
}

cpp

n = int(input())
m = int(input())
for i in range(0, n):
	for j in range(0, n):
		for k in range(0, m):
			print("hello world")

python

如果以输入的数值 $n$ 和 $m$ 的大小作为数据规模，则上面这段代码的时间复杂度为 $\Theta(n^2m)$ ．

DFS#

在对一张 $n$ 个点 $m$ 条边的图进行 DFS 时，由于每个节点和每条边都只会被访问常数次，复杂度为 $\Theta(n+m)$ ．

哪些量是常量？#

当我们要进行若干次操作时，如何判断这若干次操作是否影响时间复杂度呢？例如：

C++
Python

constexpr int N = 100000;
for (int i = 0; i < N; ++i) {
  std::cout << "hello world\n";
}

cpp

N = 100000
for i in range(0, N):
	print("hello world")

python

如果 $N$ 的大小不被看作输入规模，那么这段代码的时间复杂度就是 $O(1)$ ．

进行时间复杂度计算时，哪些变量被视作输入规模是很重要的，而所有和输入规模无关的量都被视作常量，计算复杂度时可当作 $1$ 来处理．

需要注意的是，在进行时间复杂度相关的理论性讨论时，「算法能够解决任何规模的问题」是一个基本假设（当然，在实际中，由于时间和存储空间有限，无法解决规模过大的问题）．因此，能在常量时间内解决数据规模有限的问题（例如，对于数据范围内的每个可能输入预先计算出答案）并不能使一个算法的时间复杂度变为 $O(1)$ ．

主定理 (Master Theorem)#

我们可以使用 Master Theorem 来快速求得关于递归算法的复杂度． Master Theorem 递推关系式如下

T(n) = a T\left(\frac{n}{b}\right)+f(n)\qquad \forall n > b

那么

T(n) = \begin{cases}\Theta(n^{\log_b a}) & f(n) = O(n^{\log_b (a)-\epsilon}),\epsilon > 0 \\ \Theta(f(n)) & f(n) = \Omega(n^{\log_b (a)+\epsilon}),\epsilon\ge 0\\ \Theta(n^{\log_b a}\log^{k+1} n) & f(n)=\Theta(n^{\log_b a}\log^k n),k\ge 0 \end{cases}

需要注意的是，这里的第二种情况还需要满足 regularity condition, 即 $a f(n/b) \leq c f(n)$ ，for some constant $c < 1$ and sufficiently large $n$ ．

证明思路是将规模为 $n$ 的问题，分解为 $a$ 个规模为 $(\frac{n}{b})$ 的问题，然后依次合并，直到合并到最高层．每一次合并子问题，都需要花费 $f(n)$ 的时间．

依据上文提到的证明思路，具体证明过程如下

对于第 $0$ 层（最高层），合并子问题需要花费 $f(n)$ 的时间

对于第 $1$ 层（第一次划分出来的子问题），共有 $a$ 个子问题，每个子问题合并需要花费 $f\left(\frac{n}{b}\right)$ 的时间，所以合并总共要花费 $a f\left(\frac{n}{b}\right)$ 的时间．

层层递推，我们可以写出类推树如下：

这棵树的高度为 ${\log_b n}$ ，共有 $n^{\log_b a}$ 个叶子，从而 $T(n) = \Theta(n^{\log_b a}) + g(n)$ ，其中 $g(n) = \sum_{j = 0}^{\log_{b}{n - 1}} a^{j} f(n / b^{j})$ ．

针对于第一种情况： $f(n) = O(n^{\log_b a-\epsilon})$ ，因此 $g(n) = O(n^{\log_b a})$ ．

对于第二种情况而言：首先 $g(n) = \Omega(f(n))$ ，又因为 $a f(\dfrac{n}{b}) \leq c f(n)$ ，只要 $c$ 的取值是一个足够小的正数，且 $n$ 的取值足够大，因此可以推导出： $g(n) = O(f(n)$ )．两侧夹逼可以得出， $g(n) = \Theta(f(n))$ ．

而对于第三种情况： $f(n) = \Theta(n^{\log_b a})$ ，因此 $g(n) = O(n^{\log_b a} {\log n})$ ． $T(n)$ 的结果可在 $g(n)$ 得出后显然得到．

下面举几个例子来说明主定理如何使用．

$T(n) = 2T\left(\frac{n}{2}\right) + 1$ ，那么 $a=2, b=2, {\log_2 2} = 1$ ，那么 $\epsilon$ 可以取值在 $(0, 1]$ 之间，从而满足第一种情况，所以 $T(n) = \Theta(n)$ ．
$T(n) = T\left(\frac{n}{2}\right) + n$ ，那么 $a=1, b=2, {\log_2 1} = 0$ ，那么 $\epsilon$ 可以取值在 $(0, 1]$ 之间，从而满足第二种情况，所以 $T(n) = \Theta(n)$ ．
$T(n) = T\left(\frac{n}{2}\right) + {\log n}$ ，那么 $a=1, b=2, {\log_2 1}=0$ ，那么 $k$ 可以取值为 $1$ ，从而满足第三种情况，所以 $T(n) = \Theta(\log^2 n)$ ．
$T(n) = T\left(\frac{n}{2}\right) + 1$ ，那么 $a=1, b=2, {\log_2 1} = 0$ ，那么 $k$ 可以取值为 $0$ ，从而满足第三种情况，所以 $T(n) = \Theta(\log n)$ ．

均摊复杂度#

详情可见均摊复杂度 - OI Wiki ↗．

空间复杂度#

类似地，算法所使用的空间随输入规模变化的趋势可以用 空间复杂度 来衡量．

计算复杂性理论#

此处仅基于课内 PPT 做简单介绍，更多更高深晦涩的内容请移步计算理论基础 - OI Wiki ↗。

问题#

分类#

问题分为判定问题和功能性问题，前者是只需要用“是”和“否”就能回答的问题，后者是其它更加复杂的问题。

功能性问题可以转化为判定问题，即「判断某个回答是不是该功能性问题的答案」。

规约#

一个问题 $A$ 能在一定时间内规约到另一个问题 $B$ ，就是说存在一种算法，能在一定时间内将 $A$ 的一个实例映射为 $B$ 的一个实例。最简单的例子就是：求 $2\times a$ ，可以被规约为求 $a+a$ .

详见浅谈复杂度理论中的归约(Reduction) - 知乎 ↗。

图灵机#

图灵机的严谨定义可参考计算理论基础#图灵机 - OI Wiki ↗，此处只给出直观理解：图灵机是一个具有状态、可以读取数据、根据数据进行状态转移、输出数据、并在到达指定状态时停止的自动机器。

图灵机与冯·诺依曼计算机解决问题的时间复杂度差别在多项式级别内，所以研究复杂度类时可以使用图灵机作为计算模型。

确定性图灵机#

任何情况下，每一步只能转移到一个状态的图灵机。

非确定性图灵机#

和确定型图灵机的不同，非确定型图灵机可以「同时」转移到多个状态，从而在多个「分支」并行计算，一旦这些「分支」中有一个在接受状态停机，则此非确定性图灵机接受这个输入．

复杂度类#

P 问题：能被确定性图灵机在多项式时间内解决的判定问题。

NP 问题：能被非确定性图灵机在多项式时间内解决的判定问题。

P 和 NP 问题还有一套常用的等价定义：

P 问题：能在多项式时间内解决的问题。

NP 问题：能在多项式时间内验证某个解是否正确的问题。

如果任何 NP 问题都可以在多项式时间内规约到某个问题 $H$ ，那么问题 $H$ 就是 NP-hard 的。这里的 hard 可以理解为：至少不比 NP 问题简单。

如果一个 NP-hard 问题同时也是 NP 问题，那么它就是 NP-complete 的，简称 NPC 问题。这里的 complete 可以理解为 NPC 是全部 NP 问题的代表。

如果一个 NP 问题既不是 P 问题也不是 NPC 问题，那么它就是 NP-intermidiate 的。

下面用 Eular 图呈现了 $\mathsf{P} \ne \mathsf{NP}$ 和 $\mathsf{P} = \mathsf{NP}$ 两种情况下，这几类问题的关系：

P≠NP
P=NP

学界更倾向于 $\mathsf{P} \ne \mathsf{NP}$ ，因为如果存在 NP-intermediate 问题，也即 $\mathsf{P}\cup \mathsf{NPC} \subsetneqq \mathsf{NP}$ ，那么必然 $\mathsf{P} \ne \mathsf{NP}$ . 而目前怀疑图同构问题、离散对数问题和因数分解问题是 NP-intermediate 的，但还没有证明。

注意到 $\mathsf{P}\ne\mathsf{NP}$ 时， $\mathsf{P} \cap \mathsf{NP\text{-}hard} = \varnothing$ . 这是因为，如果存在某个 P 问题同时也是 NP-hard 问题，那么一切 NP 问题都能在多项式时间内规约到这个 P 问题，从而都能在多项式时间内判定，因此 $\mathsf{P}=\mathsf{NP}$ ，矛盾。

注意到 $\mathsf{P}=\mathsf{NP}$ 时，有一部分 P 问题不是 NPC 问题。这部分问题的比例在图中被严重夸大了，实际上其占比很小。

具体地，这是因为有个别 P 问题过于平凡，导致它们甚至不是 P-complete 的（也即不是所有 P 问题都能规约到这个 P 问题），因此也就绝不可能是 NP-complete 的了。举例来说，判定问题 $a+a \overset{?}{=} 2a$ 是 P 问题（因为它是永真的，可以瞬间得到答案），但由于它的真值永远是 $1$ ，结构过于简单，因此任何可能为假的判定问题都无法规约到这个问题，因此它不是 P-complete 的。但任何非平凡（真值有两种取值）的 P 问题都是 P-complete 的。

补充#

来自上课 PPT 的表格：

Class	Full Name	Key Definition	Intuitive Understanding	Typical Example
P	Polynomial time	能被确定性图灵机在多项式时间内解决的判定问题	可以被快速解决	排序；最短路；二分图匹配； 2-适定性问题（2-SAT）；
NP	Nondeterministic Polynomial time	能被非确定性图灵机在多项式时间内解决的判定问题；等价定义：能在多项式时间内验证某个解是否正确的问题	解可以被快速验证	适定性问题（SAT）；
NPC	NP-Complete	① 是 NP 问题； ② 一切 NP 问题都能在多项式时间内规约到它	NP 问题中最难的一类	3-适定性问题（3-SAT）；背包问题；最大团问题（clique）；子集和问题（subset-sum）；寻找哈密顿回路；
NP-hard	NP-hard	一切 NP 问题都能在多项式时间内规约到它；未必是 NP 问题（可以是诸如优化问题的功能性问题)	至少不比 NP 简单	旅行商问题；停机问题；

由于目前没有证明 NP-intermediate 问题的存在，因此表中列出的 NP 问题，要么是 P 问题，要么是 NPC 问题。