《{时间管理}计算理论导引时间复杂性》由会员分享,可在线阅读,更多相关《{时间管理}计算理论导引时间复杂性(109页珍藏版)》请在金锄头文库上搜索。
1、朴秀峰 ,计算理论,第7章 时间复杂性,1,引言,Church-Turing论题:能够用总停机的Turing机计算的函数和识别的语言是可计算的(可判定的);理论可计算 计算复杂性理论研究计算模型在各种资源(主要是时间、空间等)限制下的计算能力; 实际可计算 一个可以计算的问题 需要多少时间和空间? 64层次梵塔,1秒钟移动1000片(计算机作),要多少时间? ( 264-1) / 1000=5.846 亿年,2,引言,复杂度和时间 :每秒作106的基本运算需要的时间,3,引言,Complexity: Hamilton回路问题(HC):任给一个无向图G,问G中有Hamilton回路吗? Hami
2、lton回路是指经过每一个顶点且每一个顶点只经过一次的回路。,设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
3、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 M1 M1=“对于输入串 w: 1) 扫描带子,如果在 1 的右边发现 0,就拒绝。 2) 如果带上既有
4、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
5、 是一个在所有输入上都停机的确定型图灵机。M 的运行时间或者时间复杂度,是一个函数 f : N N,其中 N 是非负整数集合, f(n) 是 M 在所有长度为 n 的输入上运行时所经过的最大步数。 若 f(n) 是 M 的运行时间,则称 M 在时间 f(n) 内运行,M 是时间图灵机。 通常使用 n 表示输入的长度。,9,渐进分析,因为算法的精确运行时间通常是一个复杂的表达式,所以一般是估计它的趋势和级别。 通过一种称为渐进分析 (asymptotic analysis) 的方便的估计形式,可以试图了解算法在长输入上的运行时间。 只考虑算法运行时间的表达式的最高项,而忽略该项的系数和其它低次项
6、,因为在在长输入上,最高次项的影响相比其它项占据主导地位。 例如,函数 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)
7、 是函数 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。log
8、bn 的值随着基数 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
9、 得 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(
10、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,就重复下一步
11、。 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)
12、步。 所以,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
13、和 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)。
14、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
15、) 如果所有 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) i
16、f (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 的复杂度与选择的计算模型有关。,23,复杂性理论与可计算性理论的区别,在可计算性理论中,丘奇-图灵论题断言,所有合理的计算模型都是等价的,即它们所判定的语言类都是相同的。 在复杂性理论中,模型的选择影响语言的时间复杂度。如在一个模型上线性时间内可判定的语言,在另一个模型上就不一定是线性时间内可判定