《计算引论2计算模型课件.ppt》由会员分享，可在线阅读，更多相关《计算引论2计算模型课件.ppt（45页珍藏版）》请在三一办公上搜索。
1、第二章 计算模型,计算复杂性RAM机器（Random Access Machine）RAM程序复杂性分析RASP机器图灵机模型 Lambda计算模型,2.1 计算复杂性,设n为自然数，f(n)是n的一个函数。O 表示量级，令O(f(n)表示不超过f(n)数量级的量。例：O(n)=常数，n1/2，3n，108n，在数量级上，这些量都不会超过变量n的量级。,2.1 计算复杂性,例：O(n2)=O(n),O(n2/3),a n2+bn+c,.在数量级上这些量都不会超过变量n2的量级。即上述这些量的数量级可以用O(n2)来表示。O(n)相对于 O(n2)可以忽略不计，表示为 O(n)O(n2),2.1
2、 计算复杂性,设：f(n)=aKnK+aK-1nK-1+a1n+a0 为n的K阶任意多项式，系数相对n来说是个常数。则：O(f(n)=O(nK)，称O(nK)为多项式数量级。,2.1 计算复杂性,量级演算性质：若A、B为量级，且AB，则（1）ABB（2）有限个B相加，BBBB（3）任意常数与B相乘，kBB,2.1 计算复杂性,求解问题 VS 识别语言（1）每个问题由多个例示集合而成；（2）每个例示可由符号串表示，构成符号串的基本符号给定；（3）一个问题可抽象为符号串的无穷集合；,2.1 计算复杂性,（4）符号串称为句子，所以问题是句子的集合，称为形式语言；（5）求解一个问题抽象为识别一个语言。
3、,2.1 计算复杂性,时间复杂性与空间复杂性（1）问题的规模用例示长度n刻画。（2）算法对时间的需求记为C(n)，对空间的 需求记为S(n)，它们都依赖于例示的长度n。,2.1 计算复杂性,（3）时间复杂性：设X是输入，|X|=n（指输入X的规模，n个基本符号），L(X)表示算法接受输入X执行计算需要的时间，则可把时间复杂性分为:最坏情况时间复杂性等概率时间复杂性概率时间复杂性,2.1 计算复杂性,1)最坏情况时间复杂性 若 即对于长度为n的输入，最坏情况下应用多少时间，也称最坏情况时间复杂性（worst-case）。,2.1 计算复杂性,例如对于n=3的情况，假设长度为3的输入共有6种，6种
4、情况下运行时间最长为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
5、 计算复杂性,一般而言，复杂度与N(问题规模)有关。O(1)：常量时间O(N)：线性时间，求解时间与问题规模呈线性关系O(log N)：求解时间与问题规模呈对数关系O(N2)：求解时间与问题规模呈二次方关系O(eN)：求解时间与问题规模呈指数关系,2.1 计算复杂性,例如，对排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)。但排序算法有很多，冒泡法是O(n2)，快速排序平均情况下是O(nlgn)等等。,2.1 计算复杂性,排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。,2.1 计算复杂性,计算复杂性
6、，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算中执行的步数或指令条数(即时间复杂度)，二是计算过程中所需要的存储单元数量(即空间复杂度)。,2.1 计算复杂性,在采用图灵提出的理想化的计算模型即图灵机作为标准的计算工具的情况下，可以非形式化地定义如下几类计算问题：P、NP、NP完全问题,2.1 计算复杂性,多项式时间复杂问题：对于给定的一个问题，若存在一个求解该问题的多项式时间算法，则称给定的问题是多项式可解问题，所有多项式时间可求解的问题的集合记为P类问题。,2.1 计算复杂性,形象地说，在多项式时间内可以验证一个解的问题称为NP问题。,2.1 计算复杂性,对一个问题，如果
7、所有的NP问题都能归结为它，则称该问题为NP完全问题。,2.2 RAM机器,RAM（Random Access Machine）机器是介于图灵机与实际数字计算机之间的机器。,2.2 RAM机器,2.2 RAM机器,RAM指令集：LOAD opr STORE opr ADD opr SUB opr MULT opr DIV opr,READ oprWRITE oprJMP labelJGTZ labelJZERO labelHALT,2.2 RAM机器,存储器映射：C(i)表示寄存器 Ri 的值操作数定义：（1）i 表示Ri寄存器的内容，即C(i)（2）*i间接寻址，操作数是Ri 的内容 j=C
8、(i)，即其值是C(C(i)，若j 0则停机（3）=i表示立即数i,2.2 RAM机器,2.2 RAM机器,操作数映射V(a):V(i)=C(i)V(*i)=C(C(i)V(=i)=i,2.2 RAM机器,RAM机的初始状态1、C(i)=0，对任意i 0；2、位置计数器指向程序P的第一条指令；3、输入串放在输入带上，读写头指向输入串的第一个符号；4、输出带空白。,2.2 RAM机器,RAM程序P：指令或带标号的指令的有限序列，并且最后一条指令为HALT。输入到输出的函数：f(x1,xn)=(y1,ym),2.2 RAM机器,指令的含义：LOAD a C(0)V(a)STORE i C(i)C(
9、0)STORE*i C(C(i)C(0)ADD a C(0)C(0)+V(a)SUB a C(0)C(0)V(a)MULT a C(0)C(0)*V(a)DIV a C(0)C(0)/V(a)取整,READ i C(i)输入带上读入一个符号，读头右移一位READ*i C(C(i)输入带上读入一个符号，读头右移一位WRITE a 输出带上当前位置 V(a)，写后写头右移一位JUMP b 位置计数器 bJGTZ b 若C(0)0，则位置计数器 bJZERO b 若C(0)=0，则位置计数器 bHALT 停机,2.3 RAM程序复杂性分析,一致性标准：为简化问题求解，定义时间单位、空间单位。假设，每
10、条指令执行需要一个时间单位，即需要时间为1；每个寄存器占用一个空间单位。,2.3 RAM程序复杂性分析,对数标准：每条指令需要执行的时间和空间与操作数的长度成正比。操作数的长度：l(k)=1当k0 l(k)=lint(log(k)+1，当k0 其中，lint()表示向下取整。,2.3 RAM程序复杂性分析,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
11、 a:l(C(0)+COST(a),WRITE a:COST(a)写带不用寻址READ i:l(i)READ*i:l(i)+l(C(i)JUMP b:1JGTZ b:l(C(0)+1/*其中1可以忽略*/JZERO b:l(C(0)HALT:1,2.3 RAM程序复杂性分析,例：输入X1 X2XiXn0，其中Xi为1或 2，判断1和2出现的个数是否相同？设计思路：读到1则加一，读到2则减一，若结果为0则个数相等。,2.3 RAM程序复杂性分析,程序如下：LOAD=0（累加器清零）STORE 2（差值寄存器2清零）READ 1（读入第一个数）REPEAT:LOAD 1（将寄存器1中的数读入累加器
12、中）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程序复杂性分析,ADD=1（因为读入的数为1，所以差值加1）STORE 2（将结果传回差值寄存器）NEXT:READ 1
13、（读入输入带上的下一个数）JMP REPEAT（跳回REPEAT进行检查）END:LOAD 2（结束，将差值寄存器的值读入累加器 中）JZERO EQUAL（如果为零，说明1和2的个数相等，跳转 到EQUAL）WRITE=0（将不相等的结果0写到输出带中）HALT（程序结束，系统停机）EQUAL:WRITE=1（相等，则输出1到输出带中）HALT（程序结束，系统停机）,2.3 RAM程序复杂性分析,分析：1、对于一致性标准来说，这个程序一共用了3个寄存器，所以空间复杂度为O(1)。在程序中，其指令共需循环n次，每次为一个时间单位，所以时间复杂度为O(n)。,2.3 RAM程序复杂性分析,2、对
14、于对数标准来说，这个程序中最多要有n个循环，在每次的指令中，空间所需值和操作数的长度成正比，在差值寄存器2中，可能达到的最大值为n（当输入数全部为1时）。另外，累加器中的值最坏情况下也会达到n（当输入数全部为1或2时），所以空间复杂度为O(logn)。而由于每条指令至多需要执行n次，所以该算法的时间复杂度为O(nlogn)。,2.3 RAM程序复杂性分析,线性算法：对于O(n)这样复杂度的算法，称为线性复杂度算法。拟线性算法：对于O(nlogn)这样复杂度的算法，称为拟线性复杂度算法。,2.3 RAM程序复杂性分析（续）,使用不同标准的情况：1、对于字符串演算的算法，即一般的非数值计算，如文档处理、编译系统等，一般采用对数标准来评价，数据长度变化剧烈。,2.3 RAM程序复杂性分析,2、对于科学计算，如解方程、矩阵等，数据一般采用科学法表示，所以一般采用一致性标准来评价，处理较为简单，并可以认为固定字长。,
