- 第7章笔记 （I）
- 7.1 度量复杂性
- 大O和小o记法
- 大O表示法
- 小o表示法
- 分析算法
- 模型间的复杂性关系
- 多带图灵机 t ( n ) t(n) t(n) ↔ {leftrightarrow} ↔ 单带图灵机 t 2 ( n ) t^2(n) t2(n)
- 非确定型单带图灵机 t ( n ) t(n) t(n) ↔ {leftrightarrow} ↔ 单带图灵机 2 t ( n ) 2^{t(n)} 2t(n)
- 7.2 P 类
- 有向图中路径存在问题
- 两个数互质判定问题
- 上下文无关语言是P类问题
计算理论导引 第7章 复杂性理论 I 的相关笔记，包括：度量复杂性、大O小o表示法、P类问题等……
第7章笔记 （I） 7.1 度量复杂性Def 7.1： M M M 是完全、确定的图灵机， M M M 的运行时间或时间复杂度是个函数 f : N → N f:N{rightarrow}N f:N→N ， f ( n ) f(n) f(n) 是 M M M 在所有长度为 n n n 的输入上运行时所经过的最大步数
大O和小o记法 大O表示法Def 7.2：（大O表示法的数学描述）设
f
f
f 和
g
g
g 是两个
N
→
R
+
N{rightarrow}R^+
N→R+ 的函数。称
f
(
n
)
=
O
(
g
(
n
)
)
f(n)=O(g(n))
f(n)=O(g(n)) ，若存在正整数
c
c
c 和
n
0
n_0
n0，使得对所有的
n
≥
n
0
n{ge}n_0
n≥n0 有：
f
(
n
)
≤
c
g
(
n
)
f(n){le}cg(n)
f(n)≤cg(n)
此时称
g
(
n
)
g(n)
g(n) 为
f
(
n
)
f(n)
f(n) 的**（渐进）上界**
（大O表示法只考虑最高次数项的影响、忽略常数因子）
多项式界： n c n^c nc ，其中 c c c 是大于 0 0 0 的常数
指数界： 2 n δ 2^{n^delta} 2nδ ，其中 δ {delta} δ 是大于 0 0 0 的实数
（大O表示法要避免overpower的表示，如本身是多项式时间量级的求解时间代价，虽然可用指数级来表示上界，但指数或阶乘级别量级的问题往往归结于难解问题；因此对于多项式级问题，尽量不要用指数级的上界表示）
小o表示法Def 7.5：（小o表示法的数学描述）设
f
f
f 和
g
g
g 是两个
N
→
R
+
N{rightarrow}R^+
N→R+ 的函数。称
f
(
n
)
=
o
(
g
(
n
)
)
f(n)=o(g(n))
f(n)=o(g(n)) ，有：
lim
n
→
∞
f
(
n
)
g
(
n
)
=
0
{lim_{nto {infty}}}{frac{f(n)}{g(n)}}=0
n→∞limg(n)f(n)=0
（大O与小o记法的界都是可以任意取的，只要满足相当于
≤
{leq}
≤ 或
<
{lt}
< 的条件）
Def 7.7：令 t : N → R + t:N{to}R^+ t:N→R+ 是一个函数。定义 时间复杂性类 T I M E ( t ( n ) ) TIME(t(n)) TIME(t(n)) 为由 O ( t ( n ) ) O(t(n)) O(t(n)) 时间的图灵机判定的所有语言的集合
P.S. 复杂性理论和可计算性理论的重大区别：丘奇—图灵论题断言，所有合理的计算模型都是等价的。但在复杂性理论中，模型的选择影响语言的时间复杂度。
（比如判定语言 L = 0 n 1 n L={0^n1^n} L=0n1n，单带图灵机时间的复杂度为 O ( n 2 ) O(n^2) O(n2) ，多带图灵机的时间复杂度为 O ( n ) O(n) O(n)）
模型间的复杂性关系 多带图灵机 t ( n ) t(n) t(n) ↔ {leftrightarrow} ↔ 单带图灵机 t 2 ( n ) t^2(n) t2(n)Th 7.8：设 t ( n ) t(n) t(n) 是一个函数， t ( n ) ≥ n t(n){ge}n t(n)≥n，则每一个 t ( n ) t(n) t(n) 时间的多带图灵机都和某一个 O ( t 2 ( n ) ) O(t^2(n)) O(t2(n)) 时间的单带图灵机等价
① 因为原来的多带图灵机 t ( n ) t(n) t(n) 步就可以执行完，所以每一条带上最长的长度为 t ( n ) t(n) t(n)
② 用单带来模拟多带的时候要用多道技术，读写头先走一遍捡起所有道上的读写头。
③ 接着，最差的情况是，单带对每一道都分别执行一遍，相当于对多带的每一带执行一遍
④ 若有 k k k 条带（ k k k 是有限的固定的常数），则单带执行步数为 t ( n ) + k × t ( n ) → O ( t ( n ) ) t(n) + k{times}t(n){to}O(t(n)) t(n)+k×t(n)→O(t(n))
⑤ 即对多带的每一步，单带需要最多相当的 t ( n ) t(n) t(n) 步，所以单带一共要 O ( t ( n ) ) × t ( n ) → O ( t 2 ( n ) ) O(t(n)){times}t(n){to}O(t^2(n)) O(t(n))×t(n)→O(t2(n))
（假定 t ( n ) ≥ n t(n){ge}n t(n)≥n 是合理的，因为至少要读一遍输入）
（时间复杂度在确定性的单带和多带图灵机上最多是 多项式 的差异）
非确定型单带图灵机 t ( n ) t(n) t(n) ↔ {leftrightarrow} ↔ 单带图灵机 2 t ( n ) 2^{t(n)} 2t(n)Th 7.10：设 t ( n ) t(n) t(n) 是一个函数， t ( n ) ≥ n t(n){ge}n t(n)≥n，则每一个 t ( n ) t(n) t(n) 时间的非确定型单带图灵机都和某一个 O ( 2 t ( n ) ) O(2^{t(n)}) O(2t(n)) 时间的单带图灵机等价
① 用单带图灵机模拟非确定图灵机，是以每一个转移函数中下一状态可能性最多的为标准，设最多可能性为 b b b
② 非确定图灵机中最坏情况下，每一步都有 b b b 中可能，单带图灵机需要模拟所有可能，所以一共要 b t ( n ) ∼ O ( 2 t ( n ) ) b^{t(n)}{sim}O(2^{t(n)}) bt(n)∼O(2t(n))
（时间复杂度在确定性的单带和非确定型单带上最多是 指数 的差异）
7.2 P 类Th 7.11：
P
P
P 是确定型单带图灵机在多项式时间内可判定的语言类，即：
P
=
∪
k
T
I
M
E
(
n
k
)
P=mathop{cup}_kTIME(n^k)
P=∪kTIME(nk)
- 对于所有与确定型单带图灵机多项式等价的计算模型来说， P P P 是不变的
- P P P 大致对应于在计算机上实际可解的那一类问题
第一条表明， P P P 是一个稳健的类，不受具体计算模型的影响；第二条表明， P P P 中的问题都有办法在多项式时间内解决；
（数据结构课程中介绍的算法基本上都属于P类问题）
P类问题和NP类问题有精确定义：
| P类问题 | NP类问题 |
| 确定型图灵机判别 | 非确定型图灵机判别 |
以下三个问题均是 P P P 类问题：
有向图中路径存在问题Th 7.12： P A T H ∈ P PATH{,}{in}{,}P PATH∈P
D
F
S
DFS
DFS （拓扑排序）算法：
M
=
M=
M= “对输入
<
G
,
s
,
t
>
{lt}G,s,t{gt}
① 准备一个队列，首先将 s s s 放入队列中，并将 s s s 标记为 v i s i t e d visited visited ；
② 每次从队列中取出一个节点，遍历该节点的所有 u n v i s i t e d unvisited unvisited 的下一节点，加入队列；
③ 当过程中遇到 t t t ，说明存在这样的路径；若队列清空，则不存在这样的路径；
分析：最多会遍历每一条边（因为要判断下一节点是否 v i s i t e d visited visited），所以复杂度为 O ( n 2 ) O(n^2) O(n2)
两个数互质判定问题Def：
R
E
L
P
R
I
M
E
=
{
<
x
,
y
>
∣
G
C
D
(
x
,
y
)
=
1
}
RELPRIME={ {lt}x,y{gt}|GCD(x,y)=1}
RELPRIME={
Th 7.13： R E L P R I M E ∈ P RELPRIME{,}{in}{,}P RELPRIME∈P
欧几里得算法：
E
=
E=
E= “对输入
<
x
,
y
>
{lt}x,y{gt}
while (y) {
x %= y;
swap(x, y);
}
cout << "(x,y)=" << x;
分析：若起始状态
x
>
y
x>y
x>y， 设
x
m
o
d
y
=
r
x{,}mod{,}y=r
xmody=r （
0
≤
r
<
y
0{le}r 不论何种情况，
x
x
x 在每次循环过程中大小至少会减半，而一次循环结束后
x
x
x 将获得
y
y
y 的值；也就是说，每进行两次循环体，
x
x
x 和
y
y
y 的值至少减少一半，执行最大次数是
2
l
o
g
2
x
2log_2x
2log2x 和
2
l
o
g
2
y
2log_2y
2log2y 中较小者，不大于
O
(
n
)
O(n)
O(n) 复习一下
C
Y
K
CYK
CYK 算法~（第6章 上下文无关语言的性质 6.3 P151）复杂度为
O
(
n
3
)
O(n^3)
O(n3) （动态规划的思想，对于某个长度为
n
n
n 的串
w
w
w ，从长度为
0
0
0 的字串开始，判定每个子串是否可以由某个
C
h
o
m
s
k
y
Chomsky
Chomsky 范式的文法得到；）
