计算引论2-计算模型1课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 计算模型,计算复杂性,RAM,机器（,Random Access Machine,）,RAM,程序复杂性分析,RASP,机器,图灵机模型,Lambda,计算模型,第二章 计算模型计算复杂性,1,2.1,计算,复杂性,设,n,为自然数，,f(n),是,n,的一个函数。,O,表示量级，令,O(f(n),表示不超过,f(n),数量级的量。,例：,O(n)=,常数，,n,1/2,，,3n,，,10,8,n,，,在数量级上，这些量都不会超过变量,n,的量级。,2.1 计算复杂性设n为自然数，f(n)是n的一个函数。O,2,2.1,计算,复杂性,例：,O(n,2,)=O(n),O(n,2/3,),a n,2,+bn+c,.,在数量级上这些量都不会超过变量,n,2,的量级。即上述这些量的数量级可以用,O(n,2,),来表示。,O(n),相对于,O(n,2,),可以忽略不计，表示为,O(n)O(n,2,),2.1 计算复杂性例：,3,2.1,计算,复杂性,设：,f(n)=a,K,n,K,+a,K-1,n,K-1,+a,1,n+a,0,为,n,的,K,阶任意多项式，系数相对,n,来说是个常数。则：,O(f(n)=O(n,K,),，称,O(n,K,),为,多项式数量级,。,2.1 计算复杂性设：f(n)=aKnK+aK-1n,4,2.1,计算,复杂性,量级演算性质：,若,A,、,B,为量级，且,AB,，则,（,1,）,A,B,B,（,2,）有限个,B,相加，,B,B,B,B,（,3,）任意常数与,B,相乘，,kB,B,2.1 计算复杂性量级演算性质：,5,2.1,计算,复杂性,求解问题,VS,识别语言,（,1,）每个问题由多个例示集合而成；,（,2,）每个例示可由符号串表示，构成符号串的基本符号给定；,（,3,）一个问题可抽象为符号串的无穷集合；,2.1 计算复杂性求解问题 VS 识别语言,6,2.1,计算,复杂性,（,4,）符号串称为句子，所以问题是,句子的集合,，称为形式语言；,（,5,）求解一个问题抽象为识别一个语言。,2.1 计算复杂性（4）符号串称为句子，所以问题是句子的集合,7,2.1,计算,复杂性,时间复杂性与空间复杂性,（,1,）问题的规模用例示长度,n,刻画。,（,2,）算法对时间的需求记为,C(n),，对空间的,需求记为,S(n),，它们都依赖于例示的长度,n,。,2.1 计算复杂性时间复杂性与空间复杂性,8,2.1,计算,复杂性,（,3,）时间复杂性：设,X,是输入，,|X|=n,（指输入,X,的规模，,n,个基本符号），,L(X),表示算法接受输入,X,执行计算需要的时间，则可把时间复杂性分为,:,最坏情况时间复杂性,等概率时间复杂性,概率时间复杂性,2.1 计算复杂性（3）时间复杂性：设X是输入，|X|=,9,2.1,计算,复杂性,1),最坏情况时间复杂性,若,即对于长度为,n,的输入，最坏情况下应用多少时间，也称最坏情况时间复杂性（,worst-case,）。,2.1 计算复杂性1)最坏情况时间复杂性,10,2.1,计算,复杂性,例如对于,n=3,的情况，假设长度为,3,的输入共有,6,种，,6,种情况下运行时间最长为,A,，则,C(3)=A,。,2.1 计算复杂性 例如对于n=3的情况，假设长度为3,11,2.1,计算,复杂性,2),等概率时间复杂性,对于,|X|=n,，,称为等概率时间复杂性（也称平均情况时间复杂性）。,2.1 计算复杂性2)等概率时间复杂性,12,3.1,计算,复杂性,3),概率时间复杂性,对于,|X|=n,，,称为概率时间复杂性，其中,p(X),表示输入,X,的分布概率。,3.1 计算复杂性3)概率时间复杂性称为概率时间复杂性，其,13,2.1,计算,复杂性,（,4,）空间复杂性，同上述讨论。,讨论：最坏情况复杂性不太合理，但分析方便；平均情况复杂性则相反，比较合理，但不易分析，目前使用大多为最坏情况复杂性。,2.1 计算复杂性 （4）空间复杂性，同上述讨论。,14,2.1,计算,复杂性,（,5,）,C(n),、,S(n),具体的解析结果很难写出，故二式的分析仅停留在数量级的分析阶段。多项式时间复杂性是指存在常数,K,，使,C(n)=O(n,k,),2.1 计算复杂性 （5）C(n)、S(n)具体的解析结果,15,2.1,计算,复杂性,一般而言，复杂度与N(问题规模)有关。,O(1)：常量时间,O(N)：线性时间，求解时间与问题规模呈线性关系,O(log N)：求解时间与问题规模呈对数关系,O(N,2,)：求解时间与问题规模呈二次方关系,O(e,N,)：求解时间与问题规模呈指数关系,2.1 计算复杂性一般而言，复杂度与N(问题规模)有关。,16,2.1,计算,复杂性,例如，对排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是,O(nlgn),。,但排序算法有很多，冒泡法是,O(n,2,),，快速排序平均情况下是,O(nlgn),等等。,2.1 计算复杂性例如，对排序问题，如果我们只能通过元素间的,17,2.1,计算,复杂性,排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。,2.1 计算复杂性排序问题的复杂性是指在所有的解决该问题的算,18,2.1,计算,复杂性,计算复杂性，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算中执行的步数或指令条数,(,即时间复杂度,),，二是计算过程中所需要的存储单元数量,(,即空间复杂度,),。,2.1 计算复杂性计算复杂性，通俗说来，就是用计算机求解问题,19,2.1,计算,复杂性,在采用图灵提出的理想化的计算模型即图灵机作为标准的计算工具的情况下，可以非形式化地定义如下几类计算问题：,P,、,NP,、,NP,完全问题,2.1 计算复杂性在采用图灵提出的理想化的计算模型即图灵机作,20,2.1,计算,复杂性,多项式时间复杂问题：对于给定的一个问题，若存在一个求解该问题的多项式时间算法，则称给定的问题是多项式可解问题，所有多项式时间可求解的问题的集合记为,P,类问题。,2.1 计算复杂性 多项式时间复杂问题：对于给定的一个问,21,2.1,计算,复杂性,形象地说，在多项式时间内可以验证一个解的问题称为,NP,问题。,2.1 计算复杂性 形象地说，在多项式时间内可以验证一个,22,2.1,计算,复杂性,对一个问题，如果所有的,NP,问题都能归结为它，则称该问题为,NP,完全问题。,2.1 计算复杂性 对一个问题，如果所有的NP问题都能归,23,2.2 RAM,机器,RAM,（,Random Access Machine,）机器是介于图灵机与实际数字计算机之间的机器。,2.2 RAM机器,24,2.2 RAM,机器,2.2 RAM机器,25,2.2 RAM,机器,RAM,指令集：,LOAD opr,STORE opr,ADD opr,SUB opr,MULT opr,DIV opr,READ opr,WRITE opr,JMP label,JGTZ label,JZERO label,HALT,2.2 RAM机器 RAM指令集：READ opr,26,2.2 RAM,机器,存储器映射：,C(i),表示寄存器,R,i,的值,操作数定义：,（,1,）,i,表示,R,i,寄存器的内容，即,C(i),（,2,）*,i,间接寻址，操作数是,R,i,的内容,j=C(i),，即其值是,C(C(i),，若,j 0,，则位置计数器,b,JZERO b,若,C(0)=0,，则位置计数器,b,HALT,停机,2.2 RAM机器指令的含义：READ i C(i),32,2.3 RAM,程序复杂性分析,一致性标准,：为简化问题求解，定义时间单位、空间单位。假设，,每条指令执行需要一个时间单位，即需要时间为,1,；,每个寄存器占用一个空间单位。,2.3 RAM程序复杂性分析一致性标准：为简化问题求解，定义,33,2.3 RAM,程序复杂性分析,对数标准,：每条指令需要执行的时间和空间与操作数的长度成正比。,操作数的长度：,l,(k)=1,当,k,0,l,(k)=lint(log(k)+1,，当,k,0,其中，,lint(),表示向下取整。,2.3 RAM程序复杂性分析 对数标准：每条指令需要执行的时,34,2.3 RAM,程序复杂性分析,操作数,a,Cost(a),i,l,(i)+,l,(C(i),*,i,l,(i)+,l,(C(i)+,l,(C(C(i),=i,l,(i),2.3 RAM程序复杂性分析操作数a Cost(a)i l,35,2.3 RAM,程序复杂性分析,时间复杂性分析：,LOAD a:COST(a),STORE i:,l,(C(0)+,l,(i),STORE*i:,l,(C(0)+,l,(i)+,l,(c(i),ADD a:,l,(C(0)+COST(a),SUB a:,l,(C(0)+COST(a),MULT a:,l,(C(0)+COST(a),DIV a:,l,(C(0)+COST(a),WRITE a:COST(a),写带不用寻址,READ i:,l,(i),READ*i:,l,(i)+,l,(C(i),JUMP b:1,JGTZ b:,l,(C(0)+1/*,其中,1,可以忽略*,/,JZERO b:,l,(C(0),HALT:1,2.3 RAM程序复杂性分析时间复杂性分析：WRITE,36,计算引论2-计算模型1课件,37,2.3 RAM,程序复杂性分析,例,：,输入,X,1,X,2,X,i,X,n,0,，其中,X,i,为,1,或,2,，判断,1,和,2,出现的个数是否相同？,设计思路：读到,1,则加一，读到,2,则减一，若结果为,0,则个数相等。,2.3 RAM程序复杂性分析例：输入X1 X2XiXn0,38,2.3 RAM,程序复杂性分析,程序如下：,LOAD=0,（累加器清零）,STORE 2,（差值寄存器,2,清零）,READ 1,（读入第一个数）,REPEAT:LOAD 1,（将寄存器,1,中的数读入累加器中）,JZERO END,（如果为零，说明输入带已无数据，程序,结束）,LOAD 1,（再次将寄存器,1,中的数读入累加器中）,SUB=1,（将读入的数减,1,，使得,1,变为,0,，,2,变为,1,）,JZERO ONE,（如果是零（原数为,1,），则跳到,ONE,）,LOAD 2,（否则，则将差值寄存器的数读入累加,器）,SUB=1,（因为是,2,，所以差值减,1,）,STORE 2,（将结果传回差值寄存器）,JMP NEXT,（跳转到,NEXT,，读入下一个数）,ONE:LOAD 2,（读入的数为,1,，则将差值寄存器的数,读入累加器）,2.3 RAM程序复杂性分析程序如下：,39,2.3 RAM,程序复杂性分析,ADD=1,（因为读入的数为,1,，所以差值加,1,）,STORE 2,（将结果传回差值寄存器）,NEXT:READ 1,（读入输入带上的下一个数）,JMP REPEAT,（跳回,REPEAT,进行检查）,END:LOAD 2,（结束，将差值寄存器的值读入累加器,中）,JZERO EQUAL,（如果为零，说明,1,和,2,的个数相等，跳转,到,EQUAL,）,WRITE=0,（将不相等的结果,0,写到输出带中）,HALT,（程序结束，系统停机）,EQUAL:WRITE=1,（相等，则输出,1,到输出带中）,HALT,（程序结束，系统停机,）,2.3 RAM程序复杂性分析,40,2.3 RAM,程序复杂性分析,分析,：,1,、,对于一致性标准来说，这个程序一共用了,3,个寄存器，所以空间复杂度为,O(1),。在程序中，其指令共需循环,n,次，每次为一个时间单位，所以时间复杂度为,O(n),。,2.3 RAM程序复杂性分析分析：,41,2