计算引论 计算模型 (2)精选文档.ppt

计算引论 计算模型本讲稿第一页，共四十六页第二章 计算模型n计算复杂性nRAM机器（RandomAccessMachine）nRAM程序复杂性分析nRASP机器n图灵机模型nLambda计算模型本讲稿第二页，共四十六页2.1 计算计算复杂性复杂性n设n为自然数，f(n)是n的一个函数。O表示量级，令O(f(n)表示不超过f(n)数量级的量。n例：O(n)=常数，n1/2，3n，108n，在数量级上，这些量都不会超过变量n的量级。本讲稿第三页，共四十六页2.1 计算计算复杂性复杂性n例：O(n2)=O(n),O(n2/3),an2+bn+c,.在数量级上这些量都不会超过变量n2的量级。即上述这些量的数量级可以用O(n2)来表示。nO(n)相对于O(n2)可以忽略不计，表示为O(n)O(n2)本讲稿第四页，共四十六页2.1 计算计算复杂性复杂性n设：f(n)=aKnK+aK-1nK-1+a1n+a0为n的K阶任意多项式，系数相对n来说是个常数。则：O(f(n)=O(nK)，称O(nK)为多项式数量级。本讲稿第五页，共四十六页2.1 计算计算复杂性复杂性n量级演算性质：若A、B为量级，且AB，则（1）ABB（2）有限个B相加，BBBB（3）任意常数与B相乘，kBB本讲稿第六页，共四十六页2.1 计算计算复杂性复杂性n求解问题 VS识别语言（1）每个问题由多个例示集合而成；（2）每个例示可由符号串表示，构成符号串的基本符号给定；（3）一个问题可抽象为符号串的无穷集合；本讲稿第七页，共四十六页2.1 计算计算复杂性复杂性（4）符号串称为句子，所以问题是句子的句子的集合集合，称为形式语言；（5）求解一个问题抽象为识别一个语言。本讲稿第八页，共四十六页2.1 计算计算复杂性复杂性n时间复杂性与空间复杂性（1）问题的规模用例示长度n刻画。（2）算法对时间的需求记为C(n)，对空间的需求记为S(n)，它们都依赖于例示的长度n。本讲稿第九页，共四十六页2.1 计算计算复杂性复杂性（3）时间复杂性：设X是输入，|X|=n（指输入X的规模，n个基本符号），L(X)表示算法接受输入X执行计算需要的时间，则可把时间复杂性分为:n最坏情况时间复杂性n等概率时间复杂性n概率时间复杂性本讲稿第十页，共四十六页2.1 计算计算复杂性复杂性1)最坏情况时间复杂性 若即对于长度为n的输入，最坏情况下应用多少时间，也称最坏情况时间复杂性（worst-case）。本讲稿第十一页，共四十六页2.1 计算计算复杂性复杂性例如对于n=3的情况，假设长度为3的输入共有6种，6种情况下运行时间最长为A，则C(3)=A。本讲稿第十二页，共四十六页2.1 计算计算复杂性复杂性2)等概率时间复杂性对于|X|=n，称为等概率时间复杂性（也称平均情况时间复杂性）。本讲稿第十三页，共四十六页3.1 计算计算复杂性复杂性3)概率时间复杂性对于|X|=n，称为概率时间复杂性，其中p(X)表示输入X的分布概率。本讲稿第十四页，共四十六页2.1 计算计算复杂性复杂性（4）空间复杂性，同上述讨论。讨论：最坏情况复杂性不太合理，但分析方便；平均情况复杂性则相反，比较合理，但不易分析，目前使用大多为最坏情况复杂性。本讲稿第十五页，共四十六页2.1 计算计算复杂性复杂性（5）C(n)、S(n)具体的解析结果很难写出，故二式的分析仅停留在数量级的分析阶段。多项式时间复杂性是指存在常数K，使C(n)=O(nk)本讲稿第十六页，共四十六页2.1 计算计算复杂性复杂性n一般而言，复杂度与N(问题规模)有关。nO(1)：常量时间nO(N)：线性时间，求解时间与问题规模呈线性关系nO(logN)：求解时间与问题规模呈对数关系nO(N2)：求解时间与问题规模呈二次方关系nO(eN)：求解时间与问题规模呈指数关系本讲稿第十七页，共四十六页2.1 计算计算复杂性复杂性n例如，对排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)。n但排序算法有很多，冒泡法是O(n2)，快速排序平均情况下是O(nlgn)等等。本讲稿第十八页，共四十六页2.1 计算计算复杂性复杂性n排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。本讲稿第十九页，共四十六页2.1 计算计算复杂性复杂性n计算复杂性，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算中执行的步数或指令条数(即时间复杂度)，二是计算过程中所需要的存储单元数量(即空间复杂度)。本讲稿第二十页，共四十六页2.1 计算计算复杂性复杂性n在采用图灵提出的理想化的计算模型即图灵机作为标准的计算工具的情况下，可以非形式化地定义如下几类计算问题：nP、NP、NP完全问题本讲稿第二十一页，共四十六页2.1 计算计算复杂性复杂性多项式时间复杂问题：对于给定的一个问题，若存在一个求解该问题的多项式时间算法，则称给定的问题是多项式可解问题，所有多项式时间可求解的问题的集合记为P类问题。本讲稿第二十二页，共四十六页2.1 计算计算复杂性复杂性形象地说，在多项式时间内可以验证一个解的问题称为NP问题。本讲稿第二十三页，共四十六页2.1 计算计算复杂性复杂性对一个问题，如果所有的NP问题都能归结为它，则称该问题为NP完全问题。本讲稿第二十四页，共四十六页2.2 RAM机器机器RAM（RandomAccessMachine）机器是介于图灵机与实际数字计算机之间的机器。本讲稿第二十五页，共四十六页2.2 RAM机器机器本讲稿第二十六页，共四十六页2.2 RAM机器机器nRAM指令集：LOADoprSTOREoprADDoprSUBoprMULToprDIVoprREADoprWRITEoprJMPlabelJGTZlabelJZEROlabelHALT本讲稿第二十七页，共四十六页2.2 RAM机器机器n存储器映射：C(i)表示寄存器Ri的值n操作数定义：（1）i表示Ri寄存器的内容，即C(i)（2）*i间接寻址，操作数是Ri的内容j=C(i)，即其值是C(C(i)，若j0，则位置计数器bJZEROb若C(0)=0，则位置计数器bHALT停机本讲稿第三十三页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析n一致性标准一致性标准：为简化问题求解，定义时间单位、空间单位。假设，每条指令执行需要一个时间单位，即需要时间为1；每个寄存器占用一个空间单位。本讲稿第三十四页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析n 对数标准对数标准：每条指令需要执行的时间和空间与操作数的长度成正比。操作数的长度：l(k)=1当k0l(k)=lint(log(k)+1，当k0其中，lint()表示向下取整。本讲稿第三十五页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析操作数aCost(a)il(i)+l(C(i)*il(i)+l(C(i)+l(C(C(i)=il(i)本讲稿第三十六页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析n时间复杂性分析：LOADa:COST(a)STOREi:l(C(0)+l(i)STORE*i:l(C(0)+l(i)+l(c(i)ADDa:l(C(0)+COST(a)SUBa:l(C(0)+COST(a)MULTa:l(C(0)+COST(a)DIVa:l(C(0)+COST(a)WRITEa:COST(a)写带不用寻址READi:l(i)READ*i:l(i)+l(C(i)JUMPb:1JGTZb:l(C(0)+1/*其中1可以忽略*/JZEROb:l(C(0)HALT:1本讲稿第三十七页，共四十六页本讲稿第三十八页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析例例：输入X1X2XiXn0，其中Xi为1或2，判断1和2出现的个数是否相同？设计思路：读到1则加一，读到2则减一，若结果为0则个数相等。本讲稿第三十九页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析程序如下：LOAD=0（累加器清零）STORE2（差值寄存器2清零）READ1（读入第一个数）REPEAT:LOAD1（将寄存器1中的数读入累加器中）JZEROEND（如果为零，说明输入带已无数据，程序结束）LOAD1（再次将寄存器1中的数读入累加器中）SUB=1（将读入的数减1，使得1变为0，2变为1）JZEROONE（如果是零（原数为1），则跳到ONE）LOAD2（否则，则将差值寄存器的数读入累加器）SUB=1（因为是2，所以差值减1）STORE2（将结果传回差值寄存器）JMPNEXT（跳转到NEXT，读入下一个数）ONE:LOAD2（读入的数为1，则将差值寄存器的数读入累加器）本讲稿第四十页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析ADD=1（因为读入的数为1，所以差值加1）STORE2（将结果传回差值寄存器）NEXT:READ1（读入输入带上的下一个数）JMPREPEAT（跳回REPEAT进行检查）END:LOAD2（结束，将差值寄存器的值读入累加器中）JZEROEQUAL（如果为零，说明1和2的个数相等，跳转到EQUAL）WRITE=0（将不相等的结果0写到输出带中）HALT（程序结束，系统停机）EQUAL:WRITE=1（相等，则输出1到输出带中）HALT（程序结束，系统停机）本讲稿第四十一页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析n分析分析：1、对于一致性标准来说，这个程序一共用了3个寄存器，所以空间复杂度为O(1)。在程序中，其指令共需循环n次，每次为一个时间单位，所以时间复杂度为O(n)。本讲稿第四十二页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析2、对于对数标准来说，这个程序中最多要有n个循环，在每次的指令中，空间所需值和操作数的长度成正比，在差值寄存器2中，可能达到的最大值为n（当输入数全部为1时）。另外，累加器中的值最坏情况下也会达到n（当输入数全部为1或2时），所以空间复杂度为O(logn)。而由于每条指令至多需要执行n次，所以该算法的时间复杂度为O(nlogn)。本讲稿第四十三页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析n线性算法：对于O(n)这样复杂度的算法，称为线性复杂度算法。n拟线性算法：对于O(nlogn)这样复杂度的算法，称为拟线性复杂度算法。本讲稿第四十四页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析（续）n使用不同标准的情况：1、对于字符串演算的算法，即一般的非数值计算，如文档处理、编译系统等，一般采用对数标准来评价，数据长度变化剧烈。本讲稿第四十五页，共四十六页2.3 RAM程序复杂性分析程序复杂性分析2、对于科学计算，如解方程、矩阵等，数据一般采用科学法表示，所以一般采用一致性标准来评价，处理较为简单，并可以认为固定字长。本讲稿第四十六页，共四十六页