计算机算法概论优秀PPT.ppt
《计算机算法概论优秀PPT.ppt》由会员分享,可在线阅读,更多相关《计算机算法概论优秀PPT.ppt(34页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 9)概率算法概率算法 10)近似算法近似算法 8)NPNP完全性完全性 6)回溯法回溯法 7)分支分支-限界法限界法 学习要点学习要点:理解算法的概念。理解算法的概念。理解什么是程序,程序与算法的区分和内理解什么是程序,程序与算法的区分和内在联系。在联系。驾驭算法的计算困难性概念。驾驭算法的计算困难性概念。驾驭算法渐近困难性的数学表述。驾驭算法渐近困难性的数学表述。驾驭用驾驭用C/C+语言描述算法的方法。语言描述算法的方法。第一讲第一讲 算法概述算法概述 20世纪50年头,西方著名的词典中还未曾收录过算法(Algorithm)一词,据西方数学史家考证,Algorithm取自于古代阿拉伯学者的
2、名著复原和化简的规则一书的作者的署名中的al-Khwarizmi,而从作品名字中的al-jabr派生出了Algebra(代数)一词。随着时间的推移,Algorithm这个词的含义,已经完全不同于它原来的含义了。一、什么是算法?一、什么是算法?一个算法是一个有穷规则的集合。这些规则规定了解一个算法是一个有穷规则的集合。这些规则规定了解决某一问题的一个运算序列。同时,一个算法应当具有五决某一问题的一个运算序列。同时,一个算法应当具有五个特性:有穷性、可行性、确定性、输入、输出。个特性:有穷性、可行性、确定性、输入、输出。1.有穷性:规则的有限性。或者说,求解问题的运算序有穷性:规则的有限性。或者说
3、,求解问题的运算序列,必需在有限的计算步后停止。列,必需在有限的计算步后停止。2.可行性:每一计算步都是基本的、可实现的。可行性:每一计算步都是基本的、可实现的。3.确定性:每一条规则都是明确、无二义的。确定性:每一条规则都是明确、无二义的。算法定义:算法定义:5.输出(输出(1):算法产生与输入相关的量。):算法产生与输入相关的量。4.输入(输入(0):算法起先执行之前指定初始值。):算法起先执行之前指定初始值。二、算法的又一描述方式二、算法的又一描述方式 设:四元组(设:四元组(Q,I,f ).其中:其中:Q:状态集合状态集合;I,:Q的子集,分别代表输入和输出的子集,分别代表输入和输出
4、f:定义在定义在Q之上的一个映射之上的一个映射。且有:若且有:若q ,则:,则:f(q)=q。1.描述描述计算序列计算序列:若对于若对于I 的每一个输入的每一个输入x,由由f 定义一个计算序列:定义一个计算序列:y0,y1,y2,。其中:其中:y0=x;yk+1=f(yk)(k 0)。若一个计算序列在第若一个计算序列在第k步终止,且步终止,且k是使是使yK 的最小整数,则称的最小整数,则称yk是由是由x产生的输出。产生的输出。2.描述算法:描述算法:一个算法是对于一个算法是对于I 中全部输入中全部输入x,都能在有穷步内终止都能在有穷步内终止的一个计算序列。的一个计算序列。f0y1Q f1y2
5、x Iykfk-1三、程序三、程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(1)。例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。四、算法困难性分析四、算法困难性分析 算法困难性=算法所须要的计算机资源算法的时间困难性T(n);算法的空间困难性S(n)。其中n是问题的规模(输入大小)。算法的时间困难性算法的时间困难性(1)最坏状况下的时间困难性 Tmax(n)=max T(I)|size(I)=n(2)最好状况下的时
6、间困难性 Tmin(n)=min T(I)|size(I)=n(3)平均状况下的时间困难性 Tavg(n)=其中I是问题的规模为n的实例,p(I)是实 例I出现的概率。假设某算法的计算时间是f(n),其中变量n可以是输入或输出量,也可以是两者之和,还可以是它们之一的某种测度(例如,数组的维数,图的边数等)。g(n)是在事前分析中确定的某个形式很简洁的函数,它是独立于机器和语言的函数,而f(n)则与机器和语言有关。定义定义1.1 假如存在两个正常数假如存在两个正常数c和和n0,对于全部的对于全部的n n0,有,有|f(n)|c|g(n)|记作记作f(n)=O(g(n)算法时间的渐近表示算法时间的
7、渐近表示当说一个算法具有当说一个算法具有O(g(n)的计算时间时,的计算时间时,指的是假如此算法用指的是假如此算法用n值不变的同一类数值不变的同一类数据在某台机器上运行时,所用的时间总据在某台机器上运行时,所用的时间总是小于是小于|g(n)|的一个常数倍。所以的一个常数倍。所以g(n)是是计算时间计算时间f(n)的一个上界函数,的一个上界函数,f(n)的数的数量级就是量级就是g(n)。当然,在确定。当然,在确定f(n)的数量的数量级时总是试图求出最小的级时总是试图求出最小的g(n),使得,使得f(n)=O(g(n)。证明:取n0=1,当n n0时,利用A(n)的定义和一个简洁的不等式,有|A(
8、n)|am|nm+|a1|n+|a0|(|am|+|am-1|/n+|a0|/nm)nm (|am|+|a0|)nm选取c=|am|+|a0|,定理马上得证。定理定理1.11.1 若若A(n)=aA(n)=am mn nm m+a+a1 1n+an+a0 0 是一个是一个m m次多次多项式,则项式,则A(n)=O(nA(n)=O(nm m)。这个定理表明,变量这个定理表明,变量n的固定阶数为的固定阶数为m的任一的任一多项式,与此多项式的最高阶多项式,与此多项式的最高阶nm同阶。因此同阶。因此计算时间为计算时间为m阶的多项式的算法,其时间都可阶的多项式的算法,其时间都可用用O(nm)来表示。来表
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 算法 概论 优秀 PPT
限制150内