计算理论导引w2时间复杂性a np及证明

1计算理论第7章时间复杂性2引言Church-Turing论题：能够用总停机的Turing机计算的函数和识别的语言是可计算的（可判定的）；理论可计算计算复杂性理论研究计算模型在各种资源（主要是时间、空间等）限制下的计算能力；

实际可计算一个可以计算的问题需要多少时间和空间？64层次梵塔，1秒钟移动1000片（计算机作），要多少时间？(264-1)/1000=5.846亿年3引言复杂度和时间：每秒作106的基本运算需要的时间N=10N=20N=30N=40N=50N=60N10-5秒2*10-5秒3*10-5秒4*10-5秒5*10-5秒6*10-5秒N210-4秒4*10-4秒9*10-4秒16*10-525*10-436*10-4N310-3秒8*10-3秒27*10-4秒64*10-30.125秒0.216秒N510-1秒3.224秒1.7分5.2分13分2N10-3秒118.9分12.7天35.7年366世纪3N0.059秒58分6.5年3855世纪2亿世纪1.3*1013世纪4引言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百年！计算复杂性理论就是要研究计算模型在各种资源限制下的计算能力。将问题划分成HardandEasy两大类。5主要内容7.1度量复杂性 大O和小o记法、分析算法、模型间的复杂性关系7.2P类 多项式时间、P中的问题举例7.3NP类

NP中的问题举例、P与NP问题7.4NP完全性 多项式时间可归约性、NP完全性的定义、库克-列文定理7.5几个NP完全问题（自学） 顶点覆盖问题、哈密顿路径问题、子集和问题6度量复杂性考察下列例子： 语言A={0k1k|k

≥0}，显然A是一个可判定的语言。 考察下面判定A的单带TMM1

M1=“对于输入串w：1)扫描带子，如果在1的右边发现0，就拒绝。2)如果带上既有0也有1，就重复下一步。3)扫描带子，删除一个0和一个1。4)如果所有1都被删除以后还有0，或者所有0都被删除以后还有1，就拒绝。否则，如果在带上既没有剩下0也没有剩下1，就接受。考察判定A的图灵机M1的算法所需的时间。7度量复杂性把算法的运行时间纯粹作为表示输入字符串的长度来计算，而不考虑其它参数。最坏情况分析（worst-caseanalysis）：考虑在某特定长度的所有输入上的最长运行时间。平均情况分析（average-caseanalysis）：考虑在某特定长度的所有输入上的运行时间的平均值。8度量复杂性定义8.1令M是一个在所有输入上都停机的确定型图灵机。M的运行时间或者时间复杂度，是一个函数

f:N

N，其中N是非负整数集合，f(n)是M在所有长度为n的输入上运行时所经过的最大步数。若f(n)是M的运行时间，则称M在时间f(n)内运行，M是时间图灵机。通常使用n表示输入的长度。9渐进分析因为算法的精确运行时间通常是一个复杂的表达式，所以一般是估计它的趋势和级别。通过一种称为渐进分析

(asymptoticanalysis)的方便的估计形式，可以试图了解算法在长输入上的运行时间。只考虑算法运行时间的表达式的最高项，而忽略该项的系数和其它低次项，因为在在长输入上，最高次项的影响相比其它项占据主导地位。例如，函数f(n)=6n3+2n2+20n+45

称f渐进地不大于n3，表达这种关系的渐进记法或大O记法是f(n)=O(n3)。10大O和小o记法定义8.2设f和g

是两个函数f，g：N

R+。称f(n)=O(g(n))，若存在正整数c和

n0，使得对所有

n≥n0

有f(n)≤cg(n)当f(n)=O(g(n))时，称g(n)是f(n)的上界，或更准确地说，

g(n)是f(n)的渐近上界，以强调没有考虑常数因子。11大O和小o记法例8.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记法例8.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比loglogn更占支配位置。f(n)

=O(n2)+O(n)等价于f(n)

=O(n2)当O出现在指数位置，如f(n)=2O(n)，代表着2cn的一个上界。f(n)=2O(logn)，代表nc。（由n=2logn

得nc=2clog2n）2O(1)代表了同样的界，因为表达式O(1)代表不超过某个固定常数的上界。14大O和小o记法我们经常导出nc

的界，c是大于0的常数。这种界称为多项式界(polynamialbound)。形如的界，当是大于0的实数时，称为指数界(exponentialbound)。大O记法指一个函数渐近地不大于另一个函数。小o记法是渐进的小于另一个函数。大O记法与小o记法的区别类似于≤和＜之间的区别。15大O和小o记法定义8.5设f和g是两个函数f,g:N

R+，如果则称f(n)=o(g(n))。换言之，f(n)=o(g(n))意味着对于任何实数c＞0，存在一个数n0，使得对所有n≥n0，f(n)＜cg(n)。16大O和小o记法例8.6

容易验证下面的等式。

1)