资源预览内容
第1页 / 共111页
第2页 / 共111页
第3页 / 共111页
第4页 / 共111页
第5页 / 共111页
第6页 / 共111页
第7页 / 共111页
第8页 / 共111页
第9页 / 共111页
第10页 / 共111页
亲,该文档总共111页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1,引言,Church-Turing论题:能够用总停机的Turing机计算的函数和识别的语言是可计算的(可判定的);理论可计算计算复杂性理论研究计算模型在各种资源(主要是时间、空间等)限制下的计算能力; 实际可计算一个可以计算的问题 需要多少时间和空间?64层次梵塔,1秒钟移动1000片(计算机作),要多少时间?( 264-1) / 1000=5.846 亿年,2,引言,复杂度和时间 :每秒作106的基本运算需要的时间,3,引言,Complexity:Hamilton回路问题(HC):任给一个无向图G,问G中有Hamilton回路吗?Hamilton回路是指经过每一个顶点且每一个顶点只经过一次的回路。,设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 度量复杂性大 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) 如果所有 1 都被删除以后还有 0,或者所有 0 都被删除以后还有 1,就拒绝。否则,如果在带上既没有剩下0也没有剩下 1,就接受。考察判定 A 的图灵机 M1 的算法所需的时间。,7,度量复杂性,把算法的运行时间纯粹作为表示输入字符串的长度来计算,而不考虑其它参数。最坏情况分析(worst-case analysis):考虑在某特定长度的所有输入上的最长运行时间。平均情况分析(average-case analysis):考虑在某特定长度的所有输入上的运行时间的平均值。,8,度量复杂性,定义7.1,令 M 是一个在所有输入上都停机的确定型图灵机。M 的运行时间或者时间复杂度,是一个函数 f : N N,其中 N 是非负整数集合, f(n) 是 M 在所有长度为 n 的输入上运行时所经过的最大步数。若 f(n) 是 M 的运行时间,则称 M 在时间 f(n) 内运行,M 是时间图灵机。通常使用 n 表示输入的长度。,9,渐进分析,因为算法的精确运行时间通常是一个复杂的表达式,所以一般是估计它的趋势和级别。通过一种称为渐进分析 (asymptotic analysis) 的方便的估计形式,可以试图了解算法在长输入上的运行时间。只考虑算法运行时间的表达式的最高项,而忽略该项的系数和其它低次项,因为在在长输入上,最高次项的影响相比其它项占据主导地位。例如,函数 f (n) = 6n3+2n2+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)。,验证该结果是否满足上面的形式定义。令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(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,大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)。,16,大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,就拒绝。否则,如果在带上既没有剩下 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 = 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; 然后从第一个 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的时间复杂性,如果图灵机有第二条带,就可以在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),因而是线性的。注意,这可能是最好的运行时间,因为光是读输入就需要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 的复杂度与选择的计算模型有关。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号