计算引论2计算模型课件.ppt
《计算引论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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算 引论 模型 课件
链接地址:https://www.31ppt.com/p-4084472.html