计算机算法概论优秀课件.ppt

《计算机算法概论优秀课件.ppt》由会员分享，可在线阅读，更多相关《计算机算法概论优秀课件.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机算法概论第1页，本讲稿共35页 9）概率算法概率算法 10）近似算法近似算法 8）NPNP完全性完全性 6）回溯法回溯法 7）分支分支-限界法限界法 第2页，本讲稿共35页学习要点学习要点:理解算法的概念。理解什么是程序，程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握用C/C+语言描述算法的方法。第一讲第一讲 算法概述算法概述第3页，本讲稿共35页 20世纪50年代，西方著名的词典中还未曾收录过算法(Algorithm)一词，据西方数学史家考证，Algorithm取自于古代阿拉伯学者的名著复原和化简的规则一书的作者的署名中的al-Khwarizm

2、i，而从作品名字中的al-jabr派生出了Algebra(代数)一词。随着时间的推移，Algorithm这个词的含义，已经完全不同于它原来的含义了。一、什么是算法？一、什么是算法？第4页，本讲稿共35页 一个算法是一个一个算法是一个有穷规则有穷规则的集合。这些规则规的集合。这些规则规定了解决某一问题的一个运算序列。同时，一个算定了解决某一问题的一个运算序列。同时，一个算法应该具有五个特性：法应该具有五个特性：有穷性、可行性、确定性、有穷性、可行性、确定性、输入、输出输入、输出。1.有穷性：规则的有限性。或者说，求解问题的有穷性：规则的有限性。或者说，求解问题的运算序列，必须在有限的计算步后停止

3、。运算序列，必须在有限的计算步后停止。2.可行性：每一计算步都是基本的、可实现的。可行性：每一计算步都是基本的、可实现的。3.确定性：每一条规则都是明确、无二义的。确定性：每一条规则都是明确、无二义的。算法定义：算法定义：第5页，本讲稿共35页 5.输出（输出（1）：算法产生与输入相关的量。）：算法产生与输入相关的量。4.输入（输入（0）：算法开始执行之前指定初始值。：算法开始执行之前指定初始值。二、算法的又一描述方式二、算法的又一描述方式 设：四元组（设：四元组（Q,I,f ).其中：其中：Q:状态集合状态集合；I,：Q的子集，分别代表输入和输出的子集，分别代表输入和输出 f:定义在定义在Q

4、之上的一个映射之上的一个映射。且有：若且有：若q ，则：，则：f(q)=q。第6页，本讲稿共35页 1.描述描述计算序列计算序列：若对于若对于I 的每一个输入的每一个输入x,由由f 定义一个计算序列：定义一个计算序列：y0,y1,y2,。其中：其中：y0=x;yk+1=f(yk)(k 0)。若一个计算序列在第若一个计算序列在第k步终止，且步终止，且k是使是使yK 的最小整数，则称的最小整数，则称yk是由是由x产生的输出。产生的输出。2.描述描述算法算法：一个算法是对于一个算法是对于I 中中所有输入所有输入x,都能在都能在有穷步有穷步内内终止终止的一个计算序列。的一个计算序列。第7页，本讲稿共3

5、5页f0y1Qf1y2 x Iykfk-1第8页，本讲稿共35页三、程序三、程序(Program)程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(1)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。第9页，本讲稿共35页四、算法复杂性分析四、算法复杂性分析 算法复杂性=算法所需要的计算机资源算法的时间复杂性T(n)；算法的空间复杂性S(n)。其中n是问题的规模（输入大小）。第10页，本讲稿共35页算法的时间复杂性算法的时间复杂性（1）最坏

6、情况最坏情况下的时间复杂性 Tmax(n)=max T(I)|size(I)=n（2）最好情况最好情况下的时间复杂性 Tmin(n)=min T(I)|size(I)=n（3）平均情况平均情况下的时间复杂性 Tavg(n)=其中I是问题的规模为n的实例，p(I)是实 例I出现的概率。第11页，本讲稿共35页假设某算法的计算时间是f(n)，其中变量n可以是输入或输出量，也可以是两者之和，还可以是它们之一的某种测度(例如，数组的维数，图的边数等)。g(n)是在事前分析中确定的某个形式很简单的函数，它是独立于机器和语言的函数，而f(n)则与机器和语言有关。定义定义1.1 如果存在两个正常数c和n0,

7、对于所有的n n0，有|f(n)|c|g(n)|记作f(n)=O(g(n)算法时间的渐近表示第12页，本讲稿共35页当说一个算法具有当说一个算法具有O(g(n)的计算时间时，的计算时间时，指的是如果此算法用指的是如果此算法用n值不变的同一类数值不变的同一类数据在某台机器上运行时，所用的时间总据在某台机器上运行时，所用的时间总是小于是小于|g(n)|的一个常数倍。所以的一个常数倍。所以g(n)是是计算时间计算时间f(n)的一个上界函数，的一个上界函数，f(n)的数的数量级就是量级就是g(n)。当然，在确定。当然，在确定f(n)的数量的数量级时总是试图求出最小的级时总是试图求出最小的g(n)，使得

8、，使得f(n)=O(g(n)。第13页，本讲稿共35页证明证明：取：取n n0 0=1,=1,当当n nn n0 0时，利用时，利用A(n)A(n)的定的定义和一个简单的不等式，有义和一个简单的不等式，有|A(n)|a|A(n)|am m|n|nm m+|a+|a1 1|n+|a|n+|a0 0|(|a (|am m|+|a|+|am-1m-1|/n+|a|/n+|a0 0|/n|/nm m)n)nm m (|a(|am m|+|a|+|a0 0|)n|)nm m选取选取c=|ac=|am m|+|a|+|a0 0|，定理立即得证。，定理立即得证。定理定理1.11.1 若若A(n)=aA(n)

9、=am mn nm m+a+a1 1n+an+a0 0 是一个是一个m m次多次多项式，则项式，则A(n)=O(nA(n)=O(nm m)。第14页，本讲稿共35页 这个定理表明，变量这个定理表明，变量n的固定阶数为的固定阶数为m的任一的任一多项式，与此多项式的最高阶多项式，与此多项式的最高阶nm同阶。因此同阶。因此计算时间为计算时间为m阶的多项式的算法，其时间都可阶的多项式的算法，其时间都可用用O(nm)来表示。来表示。事实上，只要将事实上，只要将n0取得足够大，可以证明只要取得足够大，可以证明只要c是比是比|am|大的任意一个常数，此定理都成立。大的任意一个常数，此定理都成立。第15页，本

10、讲稿共35页从计算时间上可以把算法分成两类，从计算时间上可以把算法分成两类，凡可用凡可用多项式来对其计算时间限界的算法，称为多项式来对其计算时间限界的算法，称为多多项式时间算法项式时间算法(polynomial time algorithm)(polynomial time algorithm)；而计算时间用指数函数限界的算法称为；而计算时间用指数函数限界的算法称为指指数时间算法数时间算法(exponential time algorithm)(exponential time algorithm)。第16页，本讲稿共35页指数时间算法一般有以下几种，它们关系为：指数时间算法一般有以下几种，它

11、们关系为：O(2n)O(n!)O(nn)以下六种计算时间的多项式时间算法是最为常见以下六种计算时间的多项式时间算法是最为常见的，其关系为：的，其关系为：O(1)O(1)O(longn)O(longn)O(n)O(n)O(nlongn)O(nlongn)O(nO(n2 2)O(nO(n3 3)因此，只要有人能将现在指数时间算法中因此，只要有人能将现在指数时间算法中的任何一个算法化简为多项式时间算法，的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就那就取得了一个伟大的成就!第17页，本讲稿共35页算法分析中常见的复杂性函数算法分析中常见的复杂性函数第18页，本讲稿共35页算法分析的基本

12、法则算法分析的基本法则非递归算法非递归算法：（1）for/while 循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。第19页，本讲稿共35页问题求解问题求解(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法第20页，本讲稿共35页五、算法设计的例子穷举法例1.1 百鸡问题公元5世纪末，数学家张丘建在算经中，提出这样一个问题：“鸡翁一，值钱五；鸡母一，值钱一；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母

13、、雏各几何”。第21页，本讲稿共35页l令a为公鸡只数，b为母鸡只数，c为小鸡只数l a+b+c=100 (1)l5a+3b+c/3=100 (2)lc%3=0 (3)l上述百鸡问题中，a、b、c的可能取值范围为0-100，对在此范围内的a、b、c的所有组合进行测试，凡是满足上述3个约束方程的组合，都是问题的解。第22页，本讲稿共35页输入：所购买的3种鸡的总数目n输出：满足问题的解的数目k，公鸡，母鸡，小鸡的只数g，m，s第23页，本讲稿共35页void chicken_question(int n,int&k,int g,int m,int s)int a,b,c;k=0;for(a=0;

14、a=n;a+)for(b=0;b=n;b+)for(c=0;c=n;c+)if(a+b+c=n)&(5*a+3*b+c/3=n)&(c%3=0)gk=a;mk=b;sk=c;k+;第24页，本讲稿共35页当n=100时，内循环体执行次数大于100万次考虑到n元钱只可以买到n/5只公鸡，或n/3只母鸡，有些组合可以不必考虑。而小鸡的只数又与公鸡及母鸡的只数相关，内循环可以省去。这样，算法1.1中可以改为：第25页，本讲稿共35页void chicken_problem(int n,int&k,int g,int m,int s)int i,j,a,b,c;k=0;i=n/5;j=n/3;for(

15、a=0;a=i;a+)for(b=0;b=j;b+)c=n-a-b;if(5*a+3*b+c/3=n)&(c%3=0)gk=a;mk=b;sk=c;k+第26页，本讲稿共35页例1.2 货郎担问题l某售货员要到若干个城市销售货物，已知各城市之间的距离，要求售货员选择出发的城市及旅行路线，使每一个城市仅经过一次，最后回到原出发城市，而总路程最短。l如果对任意数目的n个城市，分别用1-n的数字编号，这个问题归结为带权有向图中，寻找一条路径最短 的哈密尔顿回路问题。l思考：存储的实现方法第27页，本讲稿共35页l售货员的每一条路线，对应于城市编号1,2,n的一个排列。用一个数组来存放这个排列中的数据

16、，数组中的元素依次存放旅行路线中的城市编号。ln个城市具有n!个排列，售货员共有n!条路线可供选择。采用穷举法逐一计算每一条路线的费用，从中找出费用最小的路线，便可求出问题的解。l算法1.3 穷举法版本的货郎担问题l输入：城市个数n，费用矩阵cl输出：旅行路线t，最小费用min第28页，本讲稿共35页void salesman_problem(int n,float&min,int t,float c)int pn,i=1;float cost;min=MAx_FLoat_NUM;while(i=n!)产生n个城市的第i个排列于p;cost=路线p的费用；if(cost0;i=1,2,n）。判

17、定：是否存在一种装包方法，使装）。判定：是否存在一种装包方法，使装入背包物品的入背包物品的总效益总效益大于大于K？第34页，本讲稿共35页 （1）计算机算法设计与分析）计算机算法设计与分析 王晓东王晓东 电子工业出版社电子工业出版社 2001年年1月第月第1版版 （2）算法设计与分析）算法设计与分析 王晓东王晓东 清华大学出版社清华大学出版社 2003年年1月月第第1版版 （3）计算机算法基础（第二版）计算机算法基础（第二版）余祥宣余祥宣 等等 华中理工大学出版社华中理工大学出版社 2000年年1月第月第1版版 （4）算法导论）算法导论 （英文英文，影印版），影印版）参考书参考书 *计算理论导引计算理论导引 Introduction to the Theory of Computation （美）（美）Michael Sipser 著著 麻省理工学院麻省理工学院 张立昂等译张立昂等译 机械工业出版社机械工业出版社 2000年第一版年第一版 第35页，本讲稿共35页