计算机程序算法分析之算法概述精选PPT.ppt

《计算机程序算法分析之算法概述精选PPT.ppt》由会员分享，可在线阅读，更多相关《计算机程序算法分析之算法概述精选PPT.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机程序算法分析之算法概述第1页，此课件共42页哦关于学习与研究关于学习与研究Research(Research(研究）研究）Arch Arch Search Search Research Research算法寻找解的过程算法寻找解的过程searchsearch 递归反复的寻找最优解递归反复的寻找最优解researchresearch第2页，此课件共42页哦课程内容课程内容传统算法（硬计算方法）设计与分析：传统算法（硬计算方法）设计与分析：传统算法（硬计算方法）设计与分析：传统算法（硬计算方法）设计与分析：动态规划，贪心算法，回溯，分枝界限等动态规划，贪心算法，回溯，分枝界限等现代智能算法

2、（软计算方法）设计与分析：现代智能算法（软计算方法）设计与分析：现代智能算法（软计算方法）设计与分析：现代智能算法（软计算方法）设计与分析：计算智能（神经网络，演化计算，群体智能等）计算智能（神经网络，演化计算，群体智能等）第3页，此课件共42页哦参考书参考书1.1.王晓东王晓东 计算机算法设计与分析计算机算法设计与分析 电子工业出版社电子工业出版社2.2.郑宗汉等郑宗汉等 算法设计与分析算法设计与分析 清华大学出版社清华大学出版社3.Thomas H.Cormen et al.3.Thomas H.Cormen et al.Introduction to algorithms(Second

3、Edition)Introduction to algorithms(Second Edition)Higher Education Press&The MIT PressHigher Education Press&The MIT Press4.4.王凌王凌 智能优化算法及其应用智能优化算法及其应用 清华大学出版社清华大学出版社第4页，此课件共42页哦第第1章章 算法概述算法概述学习要点学习要点:理解算法的概念。理解算法的概念。程序与算法的区别和内在联系。程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握算法渐近复杂性的数学表述

4、。第5页，此课件共42页哦算法算法算法算法(Algorithm)(Algorithm)算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：算法是若干指令的有穷序列，满足性质：(1)(1)输入输入输入输入：有外部提供的量作为算法的输入。：有外部提供的量作为算法的输入。(2)(2)输出输出输出输出：算法产生至少一个量作为输出。：算法产生至少一个量作为输出。(3)(3)确定性确定性确定性确定性：组成算法的每条指令是清晰，无歧义的。：组成算法的每条指令是清晰，无歧义的。(4)(4)有限性有限性有限性有限性：算法中每条指令的执行次数是有限的，执

5、行每：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。条指令的时间也是有限的。第6页，此课件共42页哦程序程序程序程序(Program)(Program)程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)(4)。例如操作系统，是一个在无限循环中执行的程序，因而例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。不是一个算法。操作系统的各种任务可看成是单独的问题，每一个问题由操作系操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输

6、出结统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。果后便终止。第7页，此课件共42页哦问题求解问题求解问题求解问题求解(Problem Solving)(Problem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法第8页，此课件共42页哦算法复杂性分析算法复杂性分析算法复杂性分析算法复杂性分析 算法复杂性算法复杂性 =算法所需要的计算机资源算法所需要的计算机资源算法的时间复杂性算法的时间复杂性T T(n n)；算法的空间复杂性算法的空间复杂性S S(n n)。其中其中n n是问题的规模（输入大小）。是问题的规模（输入大小

7、）。第9页，此课件共42页哦算法的时间复杂性算法的时间复杂性算法的时间复杂性算法的时间复杂性（1 1）最坏情况最坏情况最坏情况最坏情况下的时间复杂性下的时间复杂性 T Tmaxmax(n n)=max)=max T T(I)|size(I)=(I)|size(I)=n n （2 2）最好情况最好情况最好情况最好情况下的时间复杂性下的时间复杂性 T Tminmin(n n)=min)=min T T(I)|size(I)=(I)|size(I)=n n （3 3）平均情况平均情况平均情况平均情况下的时间复杂性下的时间复杂性 T Tavgavg(n n)=)=其中其中I I是问题的规模为是问题的规

8、模为n n的实例，的实例，p p(I)(I)是实是实 例例I I出现的概率。出现的概率。第10页，此课件共42页哦算法渐近复杂性算法渐近复杂性算法渐近复杂性算法渐近复杂性T T(n n),as ,as n n;(T T(n n)-)-t t(n n)/)/T T(n n)0 0 ，as as n n;t t(n n)是是T T(n n)的渐近性态，为算法的渐近复杂性。的渐近性态，为算法的渐近复杂性。在数学上，在数学上，t t(n n)是是T T(n n)的渐近表达式，是的渐近表达式，是T T(n n)略去低阶项留略去低阶项留下的主项。它比下的主项。它比T T(n n)简单。简单。第11页，此课

9、件共42页哦渐近分析的记号渐近分析的记号渐近分析的记号渐近分析的记号在下面的讨论中，对所有在下面的讨论中，对所有n n，f f(n n)0 0，g g(n n)0 0。（1 1）渐近上界记号渐近上界记号渐近上界记号渐近上界记号OOOO(g g(n n)=)=f f(n n)|)|存在正常数存在正常数c c和和n n0 0使得对所有使得对所有n n n n0 0有：有：0 0 f f(n n)cgcg(n n)（2 2）渐近下界记号渐近下界记号渐近下界记号渐近下界记号 (g g(n n)=)=f f(n n)|)|存在正常数存在正常数c c和和n n0 0使得对所有使得对所有n n n n0 0

10、有：有：0 0 cgcg(n n)f f(n n)第12页，此课件共42页哦（3 3）非紧上界记号非紧上界记号非紧上界记号非紧上界记号o o o o(g g(n n)=)=f f(n n)|)|对于任何正常数对于任何正常数c c00，存在正数和存在正数和n n0 0 00使使得对所有得对所有n n n n0 0有：有：0 0 f f(n n)00，存在正数和存在正数和n n0 0 00使使得对所有得对所有n n n n0 0有：有：0 0 cgcg(n n)f f(n n)等价于等价于 f f(n n)/)/g g(n n)，as as n n。f f(n n)(g g(n n)g g(n n

11、)o o(f f(n n)第13页，此课件共42页哦（5 5）紧渐近界记号紧渐近界记号紧渐近界记号紧渐近界记号 (g g(n n)=)=f f(n n)|)|存在正常数存在正常数c c1 1,c,c2 2和和n n0 0使得对所有使得对所有n n n n0 0有：有：c c1 1g g(n n)f f(n n)c c2 2g g(n n)定理定理定理定理1 1：(g g(n n)=)=OO(g g(n n)(g g(n n)第14页，此课件共42页哦渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义f f(n

12、 n)=)=(g g(n n)的确切意义是：的确切意义是：f f(n n)(g g(n n)。一般情况下，等式和不等式中的渐近记号一般情况下，等式和不等式中的渐近记号(g g(n n)表示表示(g g(n n)中中的某个函数。的某个函数。例如：例如：2 2n n2 2+3+3n n+1=2+1=2n n2 2+(n n)表示表示 2 2n n2 2+3+3n n+1=2+1=2n n2 2+f f(n n)，其中，其中f f(n n)是是(n n)中某个函数。中某个函数。等式和不等式中渐近记号等式和不等式中渐近记号OO,o o,和和 的意义是类似的。的意义是类似的。第15页，此课件共42页哦渐

13、近分析中函数比较渐近分析中函数比较渐近分析中函数比较渐近分析中函数比较f f(n n)=)=OO(g g(n n)a a b;b;f f(n n)=)=(g g(n n)a a b;b;f f(n n)=)=(g g(n n)a a=b;=b;f f(n n)=)=o o(g g(n n)a a b;b.b.第16页，此课件共42页哦渐近分析记号的若干性质渐近分析记号的若干性质渐近分析记号的若干性质渐近分析记号的若干性质（1 1）传递性：）传递性：）传递性：）传递性：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

14、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)；第17页，此课件共42页哦（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)；第18页，此课件共42页哦（5 5）算术运算：）算术运算：）算术运算：）算术运算：OO(f f(n n)+

16、)+OO(g 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)。第19页，此课件共42页哦规则规则OO(f f(n n)+)+OO(g g(n n)=OO(max(maxf f(n),(n),g g(n n

17、)的的证明：证明：证明：证明：对于任意对于任意f f1 1(n n)OO(f f(n n)，存在正常数，存在正常数c c1 1和自然数和自然数n n1 1，使得对所有，使得对所有n n n n1 1，有，有f f1 1(n n)c c1 1f f(n n)。类似地，对于任意类似地，对于任意g g1 1(n n)OO(g g(n n)，存在正常数，存在正常数c c2 2和自然数和自然数n n2 2，使得对所，使得对所有有n n n n2 2，有，有g g1 1(n n)c c2 2g g(n n)。令令c c3 3=max=maxc c1 1,c c2 2，n n3 3=max=maxn n1

18、1,n n2 2，h h(n n)=max)=maxf f(n),(n),g g(n n)。则对所有的则对所有的 n n n n3 3，有，有f f1 1(n n)+)+g g1 1(n n)c c1 1f f(n n)+)+c c2 2g g(n n)c c3 3f f(n n)+)+c c3 3g g(n n)=)=c c3 3(f f(n n)+)+g g(n n)c c3 32 max2 maxf f(n),(n),g g(n n)=2 =2c c3 3h h(n n)=)=OO(max(maxf f(n),(n),g g(n n).).第20页，此课件共42页哦算法渐近复杂性分析中常

19、用函数算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数（1 1）单调函数）单调函数）单调函数）单调函数单调递增：单调递增：mm n n f f(mm)f f(n n);单调递减：单调递减：mm n n f f(mm)f f(n n););严格单调递增：严格单调递增：mm n n f f(mm)f f(n n););严格单调递减：严格单调递减：mm )f f(n n).).（2 2）取整函数）取整函数）取整函数）取整函数 x x ：不大于：不大于x x的最大整数；的最大整数；x x ：不小于：不小于x x的最小整数。的最小整数。第21页，此课件共42页哦取整函

20、数的若干性质取整函数的若干性质取整函数的若干性质取整函数的若干性质 x x-1 -1 x x x x x x 00，有：，有：n n/a a /b b =n n/abab ;n n/a a /b b =n n/ab ab ;a a/b b (a a+(+(b b-1)/-1)/b b;a a/b b (a a-(-(b b-1)/-1)/b b;f f(x x)=)=x x ,g g(x x)=)=x x 为为单调递增函数。单调递增函数。第22页，此课件共42页哦（3 3）多项式函数）多项式函数）多项式函数）多项式函数 p p(n n)=)=a a0 0+a a1 1n n+a a2 2n n

21、2 2+a ad dn nd d；a ad d0;0;p p(n n)=)=(n nd d););f f(n n)=)=OO(n nk k)f f(n n)多项式有界；多项式有界；f f(n n)=)=OO(1)(1)f f(n n)c c;k k d d p p(n n)=)=OO(n nk k););k k d d p p(n n)=)=(n nk k););k k d d p p(n n)=)=o o(n nk k););k k 0:0:a a0 0=1;=1;a a1 1=a a;a a-1-1=1/=1/a a;(a amm)n n=a amn mn;(a amm)n n=(a an

22、 n)m m;a amma an n =a am+n m+n;a a1 1 a an n为为单调递增函数单调递增函数;a a1 1 n nb b=o o(a an n)第24页，此课件共42页哦e ex x 1+1+x x;|x|x|1 1 1+1+x x e ex x 1+1+x+xx+x2 2;e ex x =1+=1+x+x+(x x2 2),as),as x x0;0;第25页，此课件共42页哦（5 5）对数函数）对数函数）对数函数）对数函数 log log n n=log=log2 2n n;lg lg n n=log=log1010n n;ln ln n n=log=loge en

23、 n;loglogk kn n=(log=(log n n)k kl;l;log log log log n n=log(log=log(log n n););for a0,b0,c0 for a0,b0,c0第26页，此课件共42页哦第27页，此课件共42页哦|x|x|1 1 for for x x -1,-1,for any for any a a 0,0,log logb bn n=o o(n na a)第28页，此课件共42页哦（6 6）阶层函数）阶层函数）阶层函数）阶层函数Stirlings approximationStirlings approximation 第29页，此课件共

24、42页哦第30页，此课件共42页哦算法分析中常见的复杂性函数算法分析中常见的复杂性函数第31页，此课件共42页哦小规模数据小规模数据第32页，此课件共42页哦中等规模数据中等规模数据第33页，此课件共42页哦执行时间随执行时间随执行时间随执行时间随n n的增长而增长的情况的增长而增长的情况的增长而增长的情况的增长而增长的情况 n n!n!n n!n!n n!n!n n!n!5120s9362ms131.72h1711.27year6720s103.62s1424h18203year75.04ms1139.9s1515day193857year840.3ms12479.0s16242day207

25、7146year1.1.多项式时间复杂度算法多项式时间复杂度算法多项式时间复杂度算法多项式时间复杂度算法 p p类问题类问题类问题类问题 2.2.指数时间复杂度算法指数时间复杂度算法指数时间复杂度算法指数时间复杂度算法 n!n!或者或者或者或者2exp(n)2exp(n)NPNP类问题类问题类问题类问题第34页，此课件共42页哦算法分析方法算法分析方法算法分析方法算法分析方法例：顺序搜索算法例：顺序搜索算法例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;re

26、turn-1;第35页，此课件共42页哦（1 1）T Tmaxmax(n n)=max)=max T T(I)|size(I)=(I)|size(I)=n n=OO(n n)（2 2）T Tminmin(n n)=min)=min T T(I)|size(I)=(I)|size(I)=n n=OO(1)(1)（3 3）在平均情况下，假设：）在平均情况下，假设：(a)(a)搜索成功的概率为搜索成功的概率为p p(0(0 p p 1)1)；(b)(b)在数组的每个位置在数组的每个位置i i(0(0 i i n n)搜索成功的概率相同，均为搜索成功的概率相同，均为 p p/n n。第36页，此课件共

27、42页哦算法分析的基本法则算法分析的基本法则非递归算法：非递归算法：非递归算法：非递归算法：（1 1）for/while for/while 循环循环循环体内计算时间循环体内计算时间*循环次数；循环次数；（2 2）嵌套循环）嵌套循环循环体内计算时间循环体内计算时间*所有循环次数；所有循环次数；（3 3）顺序语句）顺序语句各语句计算时间相加；各语句计算时间相加；（4 4）if-elseif-else语句语句if if语句计算时间和语句计算时间和elseelse语句计算时间的较大者。语句计算时间的较大者。第37页，此课件共42页哦templatevoid insertion_sort(Type*a

28、,int n)Type key;/cost times for(int i=1;i=0&ajkey)/c4 sum of ti aj+1=aj;/c5 sum of(ti-1)j-;/c6 sum og(ti-1)aj+1=key;/c7 n-1 第38页，此课件共42页哦在最好情况下，在最好情况下，t ti i=1,for 1=1,for 1 i i n n;在最坏情况下，在最坏情况下，t ti i i i+1,for 1+1,for 1 i i n n;第39页，此课件共42页哦对于输入数据对于输入数据ai=n-i,i=0,1,n-1ai=n-i,i=0,1,n-1，算法，算法insert

29、ion_sort insertion_sort 达到其最坏情形。因达到其最坏情形。因此，此，由此可见，由此可见，T Tmaxmax(n n)=)=(n n2 2)第40页，此课件共42页哦最优算法最优算法最优算法最优算法问题的计算时间下界为问题的计算时间下界为(f f(n n)，则计算时间复杂性为，则计算时间复杂性为O(O(f f(n n)的算法是最优算法。的算法是最优算法。例如，排序问题的计算时间下界为例如，排序问题的计算时间下界为(n nloglogn n)，计算时间复杂性为，计算时间复杂性为OO(n nloglogn n)的排的排序算法是最优算法。序算法是最优算法。堆排序算法是最优算法。堆排序算法是最优算法。第41页，此课件共42页哦递归算法复杂性分析递归算法复杂性分析递归算法复杂性分析递归算法复杂性分析 int int factorialfactorial(int n)(int n)if(n=0)return 1;if(n=0)return 1;return n*factorial(n-1);return n*factorial(n-1);第42页，此课件共42页哦