算法设计与分析优秀PPT.ppt

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

1、算法设计与分析算法设计与分析教材：计算机算法设计与分析教材：计算机算法设计与分析王晓东王晓东编著编著电子工业出版社电子工业出版社学时：学时：36学时学时主讲老师：马宁主讲老师：马宁计算机科学的方法论在本课程中有显明的体现：计算机科学的方法论在本课程中有显明的体现：抽象、理论和设计抽象、理论和设计3个过程，也称作个过程，也称作新的思想新的思想方法方法算法设计与分析中用到的计算机科学中普遍的算法设计与分析中用到的计算机科学中普遍的概念：概念：大问题的困难性大问题的困难性效率效率抽象的层次抽象的层次重用重用折中折中提高程序设计的水平：提高程序设计的水平：从楼上走到楼下共有从楼上走到楼下共有h 个台阶

2、，每一步有个台阶，每一步有3种走种走法：走法：走1个台阶；走个台阶；走2个台阶；走个台阶；走3个台阶。问个台阶。问可走多少种方案？可走多少种方案？要求：用递归函数来编程；要求：用递归函数来编程；输入台阶个数的语句为输入台阶个数的语句为scanf(“d”，&h);输出可走方案的种类。输出可走方案的种类。提高程序设计的水平：提高程序设计的水平：从楼上走到落下共有从楼上走到落下共有h 个台阶，每一步有个台阶，每一步有3种走种走法：走法：走1个台阶；走个台阶；走2个台阶；走个台阶；走3个台阶。问个台阶。问可走多少种方案？可走多少种方案？要求：用递归函数来编程；要求：用递归函数来编程；输入台阶个数的语句

3、为输入台阶个数的语句为scanf(“d”，&h);输出可走方案的种类。输出可走方案的种类。程序代码程序代码第第1章章算法概述算法概述学习要点学习要点学习要点学习要点:理解算法的概念。理解算法的概念。理解算法的概念。理解算法的概念。理解什么是程序，程序与算法的区分和内在联系。理解什么是程序，程序与算法的区分和内在联系。理解什么是程序，程序与算法的区分和内在联系。理解什么是程序，程序与算法的区分和内在联系。驾驭算法的计算困难性概念。驾驭算法的计算困难性概念。驾驭算法的计算困难性概念。驾驭算法的计算困难性概念。驾驭算法渐近困难性的数学表述。驾驭算法渐近困难性的数学表述。驾驭算法渐近困难性的数学表述。

4、驾驭算法渐近困难性的数学表述。算法算法(Algorithm)算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：算法是若干指令的有穷序列，满足性质：算法是若干指令的有穷序列，满足性质：算法是若干指令的有穷序列，满足性质：(1)(1)输入：有外部供应的量作为算法的输入。输入：有外部供应的量作为算法的输入。输入：有外部供应的量作为算法的输入。输入：有外部供应的量作为算法的输入。(2)(2)输出：算法产生至少一个量作为输出。输出：算法产生至少一个量作为输出。输出：算

5、法产生至少一个量作为输出。输出：算法产生至少一个量作为输出。(3)(3)确定性：组成算法的每条指令是清晰，无歧义的。确定性：组成算法的每条指令是清晰，无歧义的。确定性：组成算法的每条指令是清晰，无歧义的。确定性：组成算法的每条指令是清晰，无歧义的。(4)(4)有限性：算法中每条指令的执行次数是有限的，有限性：算法中每条指令的执行次数是有限的，有限性：算法中每条指令的执行次数是有限的，有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。执行每条指令的时间也是有限的。执行每条指令的时间也是有限的。执行每条指令的时间也是有限的。程序程序(Program)程序是算法用某种程序设计语

6、言的具体实现。程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质程序可以不满足算法的性质程序可以不满足算法的性质(4)(4)。例如操作系统，是一个在无限循环中执行的程序，例如操作系统，是一个在无限循环中执行的程序，例如操作系统，是一个在无限循环中执行的程序，例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。因而不是一个算法。因而不是一个算法。因而不是一个算法。操作系统的各种任务可看成是单独的问题，每一个操作系统的各种任务可看成是单独的问题，每一个操作系统的各种任务可

7、看成是单独的问题，每一个操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来问题由操作系统中的一个子程序通过特定的算法来问题由操作系统中的一个子程序通过特定的算法来问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。实现。该子程序得到输出结果后便终止。实现。该子程序得到输出结果后便终止。实现。该子程序得到输出结果后便终止。问题求解问题求解(ProblemSolving)证明正确性证明正确性分析算法分析算法设计程序设计程序理解问题理解问题精确解或近似解精确解或近似解选择数据结构选择数据结构算法设计策略算法设计策略设计算法设计算法算法

8、困难性分析算法困难性分析算法困难性算法困难性=算法所须要的计算机资源算法所须要的计算机资源用公式表达为：用公式表达为：C=F(n,I,A)或或C=F(n,I)算法的时间困难性算法的时间困难性T(n,I);算法的空间困难性算法的空间困难性S(n,I)。其中其中n是问题的规模（输入大小）是问题的规模（输入大小）,I是输入。是输入。算法的时间困难性算法的时间困难性（1 1）最坏状况下的时间困难性）最坏状况下的时间困难性）最坏状况下的时间困难性）最坏状况下的时间困难性Tmax(n)=maxT(I)|size(I)=nTmax(n)=maxT(I)|size(I)=n（2 2）最好状况下的时间困难性）最

9、好状况下的时间困难性）最好状况下的时间困难性）最好状况下的时间困难性Tmin(n)=minT(I)|size(I)=nTmin(n)=minT(I)|size(I)=n（3 3）平均状况下的时间困难性）平均状况下的时间困难性）平均状况下的时间困难性）平均状况下的时间困难性Tavg(n)=Tavg(n)=其中，其中，其中，其中，size(I)size(I)是问题的规模，是问题的规模，是问题的规模，是问题的规模，p(I)p(I)是实是实是实是实 例例例例I I出现的概率出现的概率出现的概率出现的概率算法渐近困难性算法渐近困难性T(n)T(n),as n,as n;/;/前提条件前提条件前提条件前提

10、条件(T(n)-t(n)/T(n)(T(n)-t(n)/T(n)0 0，as nas n;/;/定义定义定义定义t(n)t(n)是是是是T(n)T(n)的渐近性态，为算法的渐近困难性。的渐近性态，为算法的渐近困难性。的渐近性态，为算法的渐近困难性。的渐近性态，为算法的渐近困难性。在数学上，在数学上，在数学上，在数学上，t(n)t(n)是是是是T(n)T(n)的渐近表达式，是的渐近表达式，是的渐近表达式，是的渐近表达式，是T(n)T(n)略去略去略去略去低阶项留下的主项。它比低阶项留下的主项。它比低阶项留下的主项。它比低阶项留下的主项。它比T(n)T(n)简洁。简洁。简洁。简洁。渐近分析的记号渐

11、近分析的记号在下面的探讨中，对全部在下面的探讨中，对全部在下面的探讨中，对全部在下面的探讨中，对全部n n，f(n)f(n)00，g(n)g(n)00。（1 1）渐近上界记号）渐近上界记号）渐近上界记号）渐近上界记号OOO(g(n)=f(n)|O(g(n)=f(n)|存在正常数存在正常数存在正常数存在正常数c c和和和和n0n0使得对全部使得对全部使得对全部使得对全部n n n0n0有：有：有：有：00f(n)f(n)cg(n)cg(n)。记为：。记为：。记为：。记为：f(n)f(n)O(g(n)O(g(n)（2 2）渐近下界记号）渐近下界记号）渐近下界记号）渐近下界记号 (g(n)=f(n)

12、|(g(n)=f(n)|存在正常数存在正常数存在正常数存在正常数c c和和和和n0n0使得对全部使得对全部使得对全部使得对全部n n n0n0有：有：有：有：0 0cg(n)cg(n)f(n)f(n)。记为：。记为：。记为：。记为：f(n)f(n)(g(n)(g(n)（3 3）紧渐近界记号）紧渐近界记号）紧渐近界记号）紧渐近界记号(g(n)=f(n)|(g(n)=f(n)|存在正常数存在正常数存在正常数存在正常数c1,c2c1,c2和和和和n0n0使得使得使得使得对全部对全部对全部对全部n nn0n0有：有：有：有：c1g(n)c1g(n)f(n)f(n)c2g(n)c2g(n)。记为：记为：

13、记为：记为：f(n)f(n)(g(n)(g(n)f(n)f(n)(g(n)(g(n)等价于等价于等价于等价于f(n)f(n)O(g(n)O(g(n)且且且且f(n)f(n)(g(n)(g(n)渐近分析中函数比较渐近分析中函数比较渐近分析中函数比较渐近分析中函数比较f(n)=O(g(n)a b;f(n)=(g(n)a b;f(n)=(g(n)a=b;f(n)=o(g(n)a b.渐近分析记号的若干性质渐近分析记号的若干性质渐近分析记号的若干性质渐近分析记号的若干性质（1 1）传递性：）传递性：）传递性：）传递性：f f(n n)=)=(g g(n n)，g g(n n)=)=(h h(n n)f

14、 f(n n)=)=(h h(n n)；f f(n n)=)=OO(g g(n n)，g g(n n)=)=OO(h h(n n)f f(n n)=)=OO(h h(n n)；f f(n n)=)=(g g(n n)，g g(n n)=)=(h h(n n)f f(n n)=)=(h h(n n)；f f(n n)=)=o o(g g(n n)，g g(n n)=)=o o(h h(n n)f f(n n)=)=o o(h h(n n)；f f(n n)=)=(g g(n n)，g g(n n)=)=(h h(n n)f f(n n)=)=(h h(n n)；（2 2）反身性：）反身性：）反身

15、性：）反身性：f f(n n)=)=(f f(n n)；f f(n n)=)=OO(f f(n n)；f f(n n)=)=(f f(n n).).（3 3）对称性：）对称性：）对称性：）对称性：f f(n n)=)=(g g(n n)g g(n n)=)=(f f(n n).（4 4）互对称性：）互对称性：）互对称性：）互对称性：f f(n n)=)=OO(g g(n n)g g(n n)=)=(f f(n n)；f f(n n)=)=o o(g g(n n)g g(n n)=)=(f f(n n)；（5 5）算术运算：）算术运算：）算术运算：）算术运算：OO(f f(n n)+)+OO(g

16、 g(n n)=OO(max(maxf f(n),(n),g g(n n)；OO(f f(n n)+)+OO(g g(n n)=OO(f f(n)+(n)+g g(n n)；OO(f f(n n)*)*OO(g g(n n)=OO(f f(n)*(n)*g g(n n)；OO(cfcf(n n)=OO(f f(n)(n)；g g(n n)=)=OO(f f(n n)OO(f f(n n)+)+OO(g g(n n)=OO(f f(n)(n)。规则规则规则规则O(f(n)+O(g(n)=O(maxf(n),g(n)O(f(n)+O(g(n)=O(maxf(n),g(n)的证明：的证明：的证明：的

17、证明：对于随意对于随意对于随意对于随意f1(n)f1(n)O(f(n)O(f(n)，存在正常数，存在正常数，存在正常数，存在正常数c1c1和自然数和自然数和自然数和自然数n1n1，使得对全，使得对全，使得对全，使得对全部部部部n nn1n1，有，有，有，有f1(n)f1(n)c1f(n)c1f(n)。类似地，对于随意类似地，对于随意类似地，对于随意类似地，对于随意g1(n)g1(n)O(g(n)O(g(n)，存在正常数，存在正常数，存在正常数，存在正常数c2c2和自然数和自然数和自然数和自然数n2n2，使得对全部，使得对全部，使得对全部，使得对全部n nn2n2，有，有，有，有g1(n)g1(

18、n)c2g(n)c2g(n)。令令令令c3=maxc1,c2c3=maxc1,c2，n3=maxn1,n2n3=maxn1,n2，h(n)=maxf(n),g(n)h(n)=maxf(n),g(n)。则对全部的则对全部的则对全部的则对全部的nnn3n3，有，有，有，有f1(n)+g1(n)f1(n)+g1(n)c1f(n)+c2g(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n)c3f(n)+c3g(n)=c3(f(n)+g(n)c32maxf(n),g(n)c32maxf(n),g(n)=2c3h(n)=O(maxf(n),g(n).=2c3h(n)=O(m

19、axf(n),g(n).算法分析中常见的困难性函数算法分析中常见的困难性函数中等规模数据中等规模数据算法分析的基本法则算法分析的基本法则非递归算法：非递归算法：非递归算法：非递归算法：（1 1）for/whilefor/while循环循环循环循环循环体内计算时间循环体内计算时间循环体内计算时间循环体内计算时间循环次数；循环次数；循环次数；循环次数；（2 2）嵌套循环）嵌套循环）嵌套循环）嵌套循环循环体内计算时间循环体内计算时间循环体内计算时间循环体内计算时间全部循环次数；全部循环次数；全部循环次数；全部循环次数；（3 3）依次语句）依次语句）依次语句）依次语句各语句计算时间相加；各语句计算时间

20、相加；各语句计算时间相加；各语句计算时间相加；（4 4）if-elseif-else语句语句语句语句if if语句计算时间和语句计算时间和语句计算时间和语句计算时间和elseelse语句计算时间的较大者。语句计算时间的较大者。语句计算时间的较大者。语句计算时间的较大者。templatevoidinsertion_sort(Type*a,intn)Typekey;/key是哨兵是哨兵/costtimesfor(inti=1;i=0&ajkey)/c4sumoftiaj+1=aj;/c5sumof(ti-1)j-;/c6sumof(ti-1)aj+1=key;/c7n-1在最好状况下，在最好状况下

21、，在最好状况下，在最好状况下，ti=1,for1ti=1,for1in;in;在最坏状况下，在最坏状况下，在最坏状况下，在最坏状况下，titii+1,for1i+1,for1in;in;对于输入数据对于输入数据对于输入数据对于输入数据ai=n-i,i=0,1,n-1ai=n-i,i=0,1,n-1，算法，算法，算法，算法insertion_sortinsertion_sort达到其达到其达到其达到其最坏情形。因此，最坏情形。因此，最坏情形。因此，最坏情形。因此，由此可见，由此可见，由此可见，由此可见，T Tmaxmax(n n)=)=(n n2 2)最优算法最优算法问题的计算时间下界为问题的计

22、算时间下界为问题的计算时间下界为问题的计算时间下界为 (f(n)(f(n)，则计算时间困，则计算时间困，则计算时间困，则计算时间困难性为难性为难性为难性为O(f(n)O(f(n)的算法是最优算法。的算法是最优算法。的算法是最优算法。的算法是最优算法。例如，排序问题的计算时间下界为例如，排序问题的计算时间下界为例如，排序问题的计算时间下界为例如，排序问题的计算时间下界为 (nlogn)(nlogn)，计，计，计，计算时间困难性为算时间困难性为算时间困难性为算时间困难性为O(nlogn)O(nlogn)的排序算法是最优算法。的排序算法是最优算法。的排序算法是最优算法。的排序算法是最优算法。堆排序算

23、法是最优算法。堆排序算法是最优算法。堆排序算法是最优算法。堆排序算法是最优算法。递归算法困难性分析递归算法困难性分析 intfactorial(intn)intfactorial(intn)if(n=0)return1;if(n=0)return1;returnn*factorial(n-1);returnn*factorial(n-1);常规的算法基本策略常规的算法基本策略分治策略分治策略分治策略分治策略动态规划动态规划动态规划动态规划贪心算法贪心算法贪心算法贪心算法回溯法回溯法回溯法回溯法分支限界法分支限界法分支限界法分支限界法概率算法概率算法概率算法概率算法线性规划与网络流线性规划与网络

24、流线性规划与网络流线性规划与网络流NPNP完全问题完全问题完全问题完全问题算法实现题：算法实现题：算法实现题：算法实现题：统计数字问题统计数字问题统计数字问题统计数字问题.问题描述：问题描述：问题描述：问题描述：一本书的页码从自然数一本书的页码从自然数一本书的页码从自然数一本书的页码从自然数11起先依次编码直到自然数起先依次编码直到自然数起先依次编码直到自然数起先依次编码直到自然数n n。书的页码依据通常的习惯编排，每个页码都不含多书的页码依据通常的习惯编排，每个页码都不含多书的页码依据通常的习惯编排，每个页码都不含多书的页码依据通常的习惯编排，每个页码都不含多余的前导数字余的前导数字余的前导数字余的前导数字0 0。例如，第。例如，第。例如，第。例如，第66页用数字页用数字页用数字页用数字66表示，而不表示，而不表示，而不表示，而不是是是是0606或或或或006006等。数字计数问题要求对给定书的总页等。数字计数问题要求对给定书的总页等。数字计数问题要求对给定书的总页等。数字计数问题要求对给定书的总页码码码码n n，计算出书的全部页码中分别用到多少次数字，计算出书的全部页码中分别用到多少次数字，计算出书的全部页码中分别用到多少次数字，计算出书的全部页码中分别用到多少次数字0 0，1 1，2 2，9 9。