计算理论导引--时间复杂性

《计算理论导引--时间复杂性》由会员分享，可在线阅读，更多相关《计算理论导引--时间复杂性（109页珍藏版）》请在金锄头文库上搜索。

1、1,朴秀峰 ,计算理论,第7章 时间复杂性,2,引言,Church-Turing论题：能够用总停机的Turing机计算的函数和识别的语言是可计算的（可判定的）；理论可计算 计算复杂性理论研究计算模型在各种资源（主要是时间、空间等）限制下的计算能力； 实际可计算 一个可以计算的问题 需要多少时间和空间？ 64层次梵塔，1秒钟移动1000片（计算机作），要多少时间？ ( 264-1) / 1000=5.846 亿年,3,引言,复杂度和时间 ：每秒作106的基本运算需要的时间,4,引言,Complexity： Hamilton回路问题（HC）：任给一个无向图G，问G中有Hamilton回路吗？ Ha

2、milton回路是指经过每一个顶点且每一个顶点只经过一次的回路。,设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 两大类。,5,引言,co-TM recognizable（补集可识）,TM-recognizable T

3、M decidable,PSPACE,6,主要内容,7.1 度量复杂性 大 O 和小 o 记法、分析算法、模型间的复杂性关系 7.2 P类 多项式时间、P 中的问题举例 7.3 NP类 NP中的问题举例、P 与 NP 问题 7.4 NP完全性 多项式时间可归约性、NP 完全性的定义、库克-列文定理 7.5 几个NP完全问题 顶点覆盖问题、哈密顿路径问题、子集和问题,7,度量复杂性,考察下列例子： 语言 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 的算法所需的时间。,8,度量复杂性,把算法的运行时间纯粹作为表示输入字符串的长度来计算，而不考虑其它参数。 最坏情况分析（worst-case analysis）：考虑在某特定长度的所有输入上的最长运行时间。 平均情况分析（average-case analysis）：考虑在某特定长度的所有输入上的运行时间的平均值。,9,度量复杂性,定义 7.1,令

5、 M 是一个在所有输入上都停机的确定型图灵机。M 的运行时间或者时间复杂度，是一个函数 f : N N，其中 N 是非负整数集合， f(n) 是 M 在所有长度为 n 的输入上运行时所经过的最大步数。 若 f(n) 是 M 的运行时间，则称 M 在时间 f(n) 内运行，M 是时间图灵机。 通常使用 n 表示输入的长度。,10,渐进分析,因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。 通过一种称为渐进分析 (asymptotic analysis) 的方便的估计形式，可以试图了解算法在长输入上的运行时间。 只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它

6、低次项，因为在在长输入上，最高次项的影响相比其它项占据主导地位。 例如，函数 f (n) = 6n3+2n2+20n+45 称 f 渐进地不大于 n3，表达这种关系的渐进记法或大 O 记法是 f (n) = O(n3)。,11,大 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)的渐近上界，以强调没有考虑常数因子。,12,大 O 和小 o 记法,例7.3 f1

7、(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 赋什么值，始终不满足定义的要求。,13,大 O 和小 o 记法,例7.4 大O记法以一种特别的方式与对数相互影响。 通常写对数时必须指明基数(或称为对数的底)，如 x=log2n 。 这里基数 2 表明该等式等价于等式 2x=n。

8、logbn 的值随着基数 b 的改变而乘以相应的常数倍，因为有恒等式 logbn = log2n / log2b。所以，写 f(n) = O(logn) 时不必再指明基数，因为最终要忽略常数因子。,14,大 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 = 2lo

9、g n 得 nc = 2c log 2n） 2O(1) 代表了同样的界，因为表达式 O(1) 代表不超过某个固定常数的上界。,15,大O 和小o 记法,我们经常导出 nc 的界，c 是大于 0 的常数。这种界称为多项式界 (polynamial bound)。形如 的界，当 是大于 0的实数时，称为指数界(exponential bound)。 大 O 记法指一个函数渐近地不大于另一个函数。 小 o 记法是渐进的小于另一个函数。 大O记法与小o记法的区别类似于和之间的区别。,16,大O 和小o 记法,定义 7.5,设 f 和 g 是两个函数 f , g : N R+，如果 则称 f (n) =

10、 o(g(n)。换言之，f (n) = o(g(n) 意味着对于任何实数 c0，存在一个数 n0，使得对所有 nn0，f (n)cg(n)。,17,大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) 。,18,分析算法,分析语言 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

12、(n)步。 所以，M1在长度为n的输入上总共耗时为O(n)+O(n2)+O(n)，或O(n2)。换言之，它的运行时间是O(n2)。,19,时间复杂性类,语言 A = 0k1k | k0 ，ATIME(n2)， 因为 M1 在时间 O(n2) 内判定 A，而 TIME(n2) 包括所有在时间内可判定的语言。 是否存在渐近更快地判定 A 的机器呢？ 在每次扫描中删除两个 0 和两个 1，如何？,20,分析 M2 的时间复杂性,下面机器 M2 采用不同的方法，可以更快地判定 A。ATIME(nlogn)。 M2=“对输入串 w： 1) 扫描带，如果 1 的右边发现 0，就拒绝。 2) 只要在带上还有

13、 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

14、)。 ATIME(nlogn)。这个结果在单带图灵机上不可能进一步改进。 单带图灵机在o(nlogn)时间内判定的语言都是正则语言。,21,分析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 都被删除，就拒绝

15、。 4) 如果所有 0 都被删除，就接受。如果还有 0 剩下，就拒绝。”,四个步骤中每一步需要O(n)步，所以全部的运行时间是O(n)，因而是线性的。 注意，这可能是最好的运行时间，因为光是读输入就需要n步。,22,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

16、) if (sk+N!=1) return false; /相当于第二条带 O(n) return true; 判断一个串，用 O(n)时间. 使用的资源:随机存取,数组，两带图灵机，,23,总结 A 的运行时间,给出一个单带 TM M1，能够在时间 O(n2)内判定A，以及一个更快的单带 TM M2，能够在时间 O(nlogn)内判定A。两带 TM M3 能在 O(n) 时间内判定语言A。 因此 A 在单带 TM 上的时间复杂度是 O(nlogn)，在两带TM 上是 O(n)。 注意 A 的复杂度与选择的计算模型有关。,24,复杂性理论与可计算性理论的区别,在可计算性理论中，丘奇-图灵论题断言，所有合理的计算模型都是等价的，即它们所判定的语言类都是相同的。 在复杂性理论中，模型的选择影响语言的时间复杂度。如在一个模型