计算引论2计算模型课件

第二章 计算模型n计算复杂性nRAM机器（RandomAccessMachine）nRAM程序复杂性分析nRASP机器n图灵机模型nLambda计算模型第二章 计算模型计算复杂性12.1 计算计算复杂性复杂性n设n为自然数，f(n)是n的一个函数。O表示量级，令O(f(n)表示不超过f(n)数量级的量。n例：O(n)=常数，n1/2，3n，108n，在数量级上，这些量都不会超过变量n的量级。2.1 计算复杂性设n为自然数，f(n)是n的一个函数。O 22.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 计算复杂性例：32.1 计算计算复杂性复杂性n设：f(n)=aKnK+aK-1nK-1+a1n+a0为n的K阶任意多项式，系数相对n来说是个常数。则：O(f(n)=O(nK)，称O(nK)为多项式数量级。2.1 计算复杂性设：f(n)=aKnK+aK-1n42.1 计算计算复杂性复杂性n量级演算性质：若A、B为量级，且AB，则（1）ABB（2）有限个B相加，BBBB（3）任意常数与B相乘，kBB2.1 计算复杂性量级演算性质：52.1 计算计算复杂性复杂性n求解问题 VS识别语言（1）每个问题由多个例示集合而成；（2）每个例示可由符号串表示，构成符号串的基本符号给定；（3）一个问题可抽象为符号串的无穷集合；2.1 计算复杂性求解问题 VS 识别语言62.1 计算计算复杂性复杂性（4）符号串称为句子，所以问题是句子的句子的集合集合，称为形式语言；（5）求解一个问题抽象为识别一个语言。2.1 计算复杂性（4）符号串称为句子，所以问题是句子的集合72.1 计算计算复杂性复杂性n时间复杂性与空间复杂性（1）问题的规模用例示长度n刻画。（2）算法对时间的需求记为C(n)，对空间的需求记为S(n)，它们都依赖于例示的长度n。2.1 计算复杂性时间复杂性与空间复杂性82.1 计算计算复杂性复杂性（3）时间复杂性：设X是输入，|X|=n（指输入X的规模，n个基本符号），L(X)表示算法接受输入X执行计算需要的时间，则可把时间复杂性分为:n最坏情况时间复杂性n等概率时间复杂性n概率时间复杂性2.1 计算复杂性（3）时间复杂性：设X是输入，|X|=92.1 计算计算复杂性复杂性1)最坏情况时间复杂性 若即对于长度为n的输入，最坏情况下应用多少时间，也称最坏情况时间复杂性（worst-case）。2.1 计算复杂性1)最坏情况时间复杂性102.1 计算计算复杂性复杂性例如对于n=3的情况，假设长度为3的输入共有6种，6种情况下运行时间最长为A，则C(3)=A。2.1 计算复杂性 例如对于n=3的情况，假设长度为3112.1 计算计算复杂性复杂性2)等概率时间复杂性对于|X|=n，称为等概率时间复杂性（也称平均情况时间复杂性）。2.1 计算复杂性2)等概率时间复杂性123.1 计算计算复杂性复杂性3)概率时间复杂性对于|X|=n，称为概率时间复杂性，其中p(X)表示输入X的分布概率。3.1 计算复杂性3)概率时间复杂性称为概率时间复杂性，其132.1 计算计算复杂性复杂性（4）空间复杂性，同上述讨论。讨论：最坏情况复杂性不太合理，但分析方便；平均情况复杂性则相反，比较合理，但不易分析，目前使用大多为最坏情况复杂性。2.1 计算复杂性 （4）空间复杂性，同上述讨论。142.1 计算计算复杂性复杂性（5）C(n)、S(n)具体的解析结果很难写出，故二式的分析仅停留在数量级的分析阶段。多项式时间复杂性是指存在常数K，使C(n)=O(nk)2.1 计算复杂性 （5）C(n)、S(n)具体的解析结果152.1 计算计算复杂性复杂性n一般而言，复杂度与N(问题规模)有关。nO(1)：常量时间nO(N)：线性时间，求解时间与问题规模呈线性关系nO(logN)：求解时间与问题规模呈对数关系nO(N2)：求解时间与问题规模呈二次方关系nO(eN)：求解时间与问题规模呈指数关系2.1 计算复杂性一般而言，复杂度与N(问题规模)有关。162.1 计算计算复杂性复杂性n例如，对排序问题，如果我们只能通过元素间的相互比较来确定元素间的相互位置，而没有其他的附加可用信息，则排序问题的复杂性是O(nlgn)。n但排序算法有很多，冒泡法是O(n2)，快速排序平均情况下是O(nlgn)等等。2.1 计算复杂性例如，对排序问题，如果我们只能通过元素间的172.1 计算计算复杂性复杂性n排序问题的复杂性是指在所有的解决该问题的算法中最好算法的复杂性。2.1 计算复杂性排序问题的复杂性是指在所有的解决该问题的算182.1 计算计算复杂性复杂性n计算复杂性，通俗说来，就是用计算机求解问题的难易程度。其度量标准：一是计算中执行的步数或指令条数(即时间复杂度)，二是计算过程中所需要的存储单元数量(即空间复杂度)。2.1 计算复杂性计算复杂性，通俗说来，就是用计算机求解问题192.1 计算计算复杂性复杂性n在采用图灵提出的理想化的计算模型即图灵机作为标准的计算工具的情况下，可以非形式化地定义如下几类计算问题：nP、NP、NP完全问题2.1 计算复杂性在采用图灵提出的理想化的计算模型即图灵机作202.1 计算计算复杂性复杂性多项式时间复杂问题：对于给定的一个问题，若存在一个求解该问题的多项式时间算法，则称给定的问题是多项式可解问题，所有多项式时间可求解的问题的集合记为P类问题。2.1 计算复杂性 多项式时间复杂问题：对于给定的一个问212.1 计算计算复杂性复杂性形象地说，在多项式时间内可以验证一个解的问题称为NP问题。2.1 计算复杂性 形象地说，在多项式时间内可以验证一个222.1 计算计算复杂性复杂性对一个问题，如果所有的NP问题都能归结为它，则称该问题为NP完全问题。2.1 计算复杂性 对一个问题，如果所有的NP问题都能归232.2 RAM机器机器RAM（RandomAccessMachine）机器是介于图灵机与实际数字计算机之间的机器。2.2 RAM机器242.2 RAM机器机器2.2 RAM机器252.2 RAM机器机器nRAM指令集：LOADoprSTOREoprADDoprSUBoprMULToprDIVoprREADoprWRITEoprJMPlabelJGTZlabelJZEROlabelHALT2.2 RAM机器 RAM指令集：READ opr262.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.2 RAM机器指令的含义：READ i C(i)322.3 RAM程序复杂性分析程序复杂性分析n一致性标准一致性标准：为简化问题求解，定义时间单位、空间单位。假设，每条指令执行需要一个时间单位，即需要时间为1；每个寄存器占用一个空间单位。2.3 RAM程序复杂性分析一致性标准：为简化问题求解，定义332.3 RAM程序复杂性分析程序复杂性分析n 对数标准对数标准：每条指令需要执行的时间和空间与操作数的长度成正比。操作数的长度：l(k)=1当k0l(k)=lint(log(k)+1，当k0其中，lint()表示向下取整。2.3 RAM程序复杂性分析 对数标准：每条指令需要执行的时342.3 RAM程序复杂性分析程序复杂性分析操作数aCost(a)il(i)+l(C(i)*il(i)+l(C(i)+l(C(C(i)=il(i)2.3 RAM程序复杂性分析操作数a Cost(a)i l352.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)WRITE a:COST(a)写带不用寻址READi:l(i)READ*i:l(i)+l(C(i)JUMPb:1JGTZb:l(C(0)+1/*其中1可以忽略*/JZEROb:l(C(0)HALT:12.3 RAM程序复杂性分析时间复杂性分析：WRITE 36计算引论2计算模型课件372.3 RAM程序复杂性分析程序复杂性分析例例：输入X1X2XiXn0，其中Xi为1或2，判断1和2出现的个数是否相同？设计思路：读到1则加一，读到2则减一，若结果为0则个数相等。2.3 RAM程序复杂性分析例：输入X1 X2XiXn0382.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程序复杂性分析程序如下：392.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程序复杂性分析402.3 RAM程序复杂性分析程序复杂性分析n分析分析：1、对于一致性标准来说，这个程序一共用了3个寄存器，所以空间复杂度为O(1)。在程序中，其指令共需循环n次，每次为一个时间单位，所以时间复杂度为O(n)。2.3 RAM程序复杂性分析分析：412.3 RAM程序复杂性分析程序复杂性分析2、对于对数标准来说，这个程序中最多要有n个循环，在每次的指令中，空间所需值和操作数的长度成正比，在差值寄存器2中，可能达到的最大值为n（当输入数全部为1时）。另外，累加器中的值最坏情况下也会达到n（当输入数全部为1或2时），所以空间复杂度为O(logn)。而由于每条指令至多需要执行n次，所以该算法的时间复杂度为O(nlogn)。2.3 RAM程序复杂性分析2、对于对数标准来说，这个程序中422.3 RAM程序复杂性分析程序复杂性分析n线性算法：对于O(n)这样复杂度的算法，称为线性复杂度算法。n拟线性算法：对于O(nlogn)这样复杂度的算法，称为拟线性复杂度算法。2.3 RAM程序复杂性分析线性算法：对于O(n)这样复杂度432.3 RAM程序复杂性分析程序复杂性分析（续）n使用不同标准的情况：1、对于字符串演算的算法，即一般的非数值计算，如文档处理、编译系统等，一般采用对数标准来评价，数据长度变化剧烈。2.3 RAM程序复杂性分析（续）使用不同标准的情况：442.3 RAM程序复杂性分析程序复杂性分析2、对于科学计算，如解方程、矩阵等，数据一般采用科学法表示，所以一般采用一致性标准来评价，处理较为简单，并可以认为固定字长。2.3 RAM程序复杂性分析 2、对于科学计算，如解方程45