《计算理论导引 7 时间复杂性》由会员分享，可在线阅读，更多相关《计算理论导引 7 时间复杂性（111页珍藏版）》请在金锄头文库上搜索。
1、1,引言,Church-Turing论题：能够用总停机的Turing机计算的函数和识别的语言是可计算的（可判定的）；理论可计算计算复杂性理论研究计算模型在各种资源（主要是时间、空间等）限制下的计算能力； 实际可计算一个可以计算的问题 需要多少时间和空间？64层次梵塔，1秒钟移动1000片（计算机作），要多少时间？( 264-1) / 1000=5.846 亿年,2,引言,复杂度和时间 ：每秒作106的基本运算需要的时间,3,引言,Complexity：Hamilton回路问题（HC）：任给一个无向图G，问G中有Hamilton回路吗？Hamilton回路是指经过每一个顶点且每一个顶点只经过一次
2、的回路。,设G有n个顶点，由于回路没有始点和终点，可以任意定一个顶点作为排列的第一个顶点，共有（n-1）！个排列。当n=25时，24！=6.2*1023.假设用一台超级计算机计算，每秒可以检查1亿个排列。每年有3.15*107秒，不停地工作，每年可以检查3.15*1015个排列。检查完所有的排列需要1.97*108年，即1亿9千7百年！计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划分成Hard and Easy 两大类。,4,引言,co-TM recognizable（补集可识）,TM-recognizable TM decidable,PSPACE,5,主要内容,7.1
3、 度量复杂性大 O 和小 o 记法、分析算法、模型间的复杂性关系7.2 P类多项式时间、P 中的问题举例7.3 NP类NP中的问题举例、P 与 NP 问题7.4 NP完全性多项式时间可归约性、NP 完全性的定义、库克-列文定理7.5 几个NP完全问题顶点覆盖问题、哈密顿路径问题、子集和问题,6,度量复杂性,考察下列例子：语言 A = 0k1k | k 0 ，显然 A 是一个可判定的语言。考察下面判定A的单带 TM M1M1=“对于输入串 w：1) 扫描带子，如果在 1 的右边发现 0，就拒绝。2) 如果带上既有 0 也有 1，就重复下一步。3) 扫描带子，删除一个 0 和一个 1。4) 如果所
4、有 1 都被删除以后还有 0，或者所有 0 都被删除以后还有 1，就拒绝。否则，如果在带上既没有剩下0也没有剩下 1，就接受。考察判定 A 的图灵机 M1 的算法所需的时间。,7,度量复杂性,把算法的运行时间纯粹作为表示输入字符串的长度来计算，而不考虑其它参数。最坏情况分析（worst-case analysis）：考虑在某特定长度的所有输入上的最长运行时间。平均情况分析（average-case analysis）：考虑在某特定长度的所有输入上的运行时间的平均值。,8,度量复杂性,定义7.1,令 M 是一个在所有输入上都停机的确定型图灵机。M 的运行时间或者时间复杂度，是一个函数 f : N
5、 N，其中 N 是非负整数集合， f(n) 是 M 在所有长度为 n 的输入上运行时所经过的最大步数。若 f(n) 是 M 的运行时间，则称 M 在时间 f(n) 内运行，M 是时间图灵机。通常使用 n 表示输入的长度。,9,渐进分析,因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。通过一种称为渐进分析 (asymptotic analysis) 的方便的估计形式，可以试图了解算法在长输入上的运行时间。只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它低次项，因为在在长输入上，最高次项的影响相比其它项占据主导地位。例如，函数 f (n) = 6n3+2n2+
6、20n+45称 f 渐进地不大于 n3，表达这种关系的渐进记法或大 O 记法是 f (n) = O(n3)。,10,大 O 和小 o记法,定义7.2,设 f 和 g 是两个函数 f ，g： N R+。称f(n)=O(g(n)，若存在正整数 c 和 n0，使得对所有 nn0 有f(n) cg(n)当 f(n)=O(g(n) 时，称 g(n) 是 f(n) 的上界，或更准确地说， g(n)是 f(n)的渐近上界，以强调没有考虑常数因子。,11,大 O 和小 o 记法,例7.3 f1(n) 是函数 5n3+2n2+22n+6。保留最高次项 5n3，并且舍去它的系数5，得到 f1=O(n3)。,验证该
7、结果是否满足上面的形式定义。令c=6，n0=10，则对于所有n 10，有 5n3+2n2+22n+6 6n3。此外，有 f1=O(n4)，因为 n4 比 n3 大，它也是 f1 的一个渐近上界。但是 f1 不等于 O(n2)，不论给 c 和 n0 赋什么值，始终不满足定义的要求。,12,大 O 和小 o 记法,例7.4 大O记法以一种特别的方式与对数相互影响。通常写对数时必须指明基数(或称为对数的底)，如 x=log2n 。这里基数 2 表明该等式等价于等式 2x=n。logbn 的值随着基数 b 的改变而乘以相应的常数倍，因为有恒等式 logbn = log2n / log2b。所以，写 f
8、(n) = O(logn) 时不必再指明基数，因为最终要忽略常数因子。,13,大 O 和小 o 记法,令 f2(n) 是函数 3nlog2n+5nlog2log2n+2。 此时 f2(n) =O(nlogn)，因为 logn 比 log logn更占支配位置。f(n) =O(n2)+ O(n) 等价于 f(n) =O(n2)当 O 出现在指数位置，如 f(n) =2O(n)，代表着 2cn 的一个上界。f(n) =2O(logn)，代表 nc。（由 n = 2log n 得 nc = 2c log 2n）2O(1) 代表了同样的界，因为表达式 O(1) 代表不超过某个固定常数的上界。,14,大
9、O 和小o 记法,我们经常导出 nc 的界，c 是大于 0 的常数。这种界称为多项式界 (polynamial bound)。形如 的界，当 是大于 0的实数时，称为指数界(exponential bound)。大 O 记法指一个函数渐近地不大于另一个函数。小 o 记法是渐进的小于另一个函数。大O记法与小o记法的区别类似于和之间的区别。,15,大O 和小o 记法,定义7.5,设 f 和 g 是两个函数 f , g : N R+，如果则称 f (n) = o(g(n)。换言之，f (n) = o(g(n) 意味着对于任何实数 c0，存在一个数 n0，使得对所有 nn0，f (n)cg(n)。,1
10、6,大O 和小o 记法,例7.6 容易验证下面的等式。 1) 2) n = o(nlog(logn) 3) nlog(logn) = o(nlogn) 4) nlogn = o(n2) 5) n2 = o(n3) 但是，f(n) 不会等于o(f(n) 。,17,分析算法,分析语言 A = 0k1k | k 0 对应的图灵机算法。M1 = “对于输入串 w：1) 扫描带子，如果在 1 的右边发现 0，就拒绝。2) 如果带上既有 0 也有 1，就重复下一步。3) 扫描带子，删除一个 0 和一个 1。4) 如果所有 1 都被删除以后还有 0，或者所有 0 都被删除以后还有 1，就拒绝。否则，如果在带
11、上既没有剩下 0 也没有剩下 1，就接受。,步骤1中，机器扫描带以验证输入的形式是0*1*。执行这次扫描需要n步。读写头重新放置在带的左端另外需要n步。共需要2n步。即O(n)步。在步骤2和3中，机器反复扫描带，在每一次扫描中删除一个0和一个1。每一次扫描需要O(n)步。因为每一次扫描删除两个符号，所以最多扫描n/2次。于是步骤2和3需要的全部时间是(n/2)O(n)=O(n2)步。在步骤4中，机器扫描一次来决定是接受还是拒绝。最多需要O(n)步。所以，M1在长度为n的输入上总共耗时为O(n)+O(n2)+O(n)，或O(n2)。换言之，它的运行时间是O(n2)。,18,时间复杂性类,语言 A
12、 = 0k1k | k0 ，ATIME(n2)，因为 M1 在时间 O(n2) 内判定 A，而 TIME(n2) 包括所有在时间内可判定的语言。是否存在渐近更快地判定 A 的机器呢？在每次扫描中删除两个 0 和两个 1，如何？,19,分析 M2 的时间复杂性,下面机器 M2 采用不同的方法，可以更快地判定 A。ATIME(nlogn)。M2=“对输入串 w：1) 扫描带，如果 1 的右边发现 0，就拒绝。2) 只要在带上还有 0 和 1，就重复下面的步骤。3) 扫描带，检查剩余的 0 和 1 的总数是偶数还是奇数。 若是奇数，就拒绝。4) 再次扫描带，从第一个 0 开始，隔一个删除一个 0；
13、然后从第一个 1 开始，隔一个删除一个 1.5) 如果带上不再有 0 和 1，就接受。否则拒绝。”,首先注意，每一步都消耗 O(n) 的时间。步骤1和5执行一次，共需要O(n)时间。步骤4在每一次执行时至少删除一半的0和1，所以至多1+log2n次循环就可以把全部字符删除。于是，步骤2、3和4总共消耗时间(1+log2n) O(n)，即O(nlogn)。M2的运行时间是O(n) +O(nlogn)= O(nlogn)。 ATIME(nlogn)。这个结果在单带图灵机上不可能进一步改进。单带图灵机在o(nlogn)时间内判定的语言都是正则语言。,20,分析M3的时间复杂性,如果图灵机有第二条带，
14、就可以在O(n)时间（也称为线性时间）内判定语言A。下面的两带图灵机TM M3在线性时间内判定A。M3 = “ 对于输入串 w：1) 扫描带，如果 1 的右边发现 0，就拒绝。2) 扫描带 1 上的 0，直到第一个 1 时停止，同时把 0 复制到带 2 上。3) 扫描带 1 上的 1 直到输入的末尾。每次从带 1 上读到一个 1，就在带 2 上删除一个 0，如果在读完 1 之前所有的 0 都被删除，就拒绝。4) 如果所有 0 都被删除，就接受。如果还有 0 剩下，就拒绝。”,四个步骤中每一步需要O(n)步，所以全部的运行时间是O(n)，因而是线性的。注意，这可能是最好的运行时间，因为光是读输入
15、就需要n步。,21,A 的 C 程序,A = 0k1k | k=0,1,2, . 先用用C语言写程序判断串 s 是否 0k1k Bool M(char *s) int L=strlen(s) /扫描一遍 O(n) if (L%2)!=0 return false; /长度不是偶数 else N=L/2; for( k=1;kN; k+) / if (sk !=0) return false; /O(n) if (sk+N!=1) return false; /相当于第二条带 O(n) return true; 判断一个串，用 O(n)时间. 使用的资源:随机存取,数组，两带图灵机，,22,总结 A 的运行时间,给出一个单带 TM M1，能够在时间 O(n2)内判定A，以及一个更快的单带 TM M2，能够在时间 O(nlogn)内判定A。两带 TM M3 能在 O(n) 时间内判定语言A。因此 A 在单带 TM 上的时间复杂度是 O(nlogn)，在两带TM 上是 O(n)。注意 A 的复杂度与选择的计算模型有关。,
