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

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

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

2、算智能（神经网络，演化计算，群体智能等）本讲稿第三页，共四十二页参考书参考书1.1.王晓东王晓东 计算机算法设计与分析计算机算法设计与分析 电子工业出版社电子工业出版社2.2.郑宗汉等郑宗汉等 算法设计与分析算法设计与分析 清华大学出版社清华大学出版社3.Thomas H.Cormen et al.3.Thomas H.Cormen et al.Introduction to algorithms(Second Edition)Introduction to algorithms(Second Edition)Higher Education Press&The MIT PressHigher

3、 Education Press&The MIT Press4.4.王凌王凌 智能优化算法及其应用智能优化算法及其应用 清华大学出版社清华大学出版社本讲稿第四页，共四十二页第第1章章 算法概述算法概述学习要点学习要点:理解算法的概念。理解算法的概念。程序与算法的区别和内在联系。程序与算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。掌握算法渐近复杂性的数学表述。本讲稿第五页，共四十二页算法算法算法算法(Algorithm)(Algorithm)算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序

4、列，满足性质：算法是若干指令的有穷序列，满足性质：(1)(1)输入输入输入输入：有外部提供的量作为算法的输入。：有外部提供的量作为算法的输入。(2)(2)输出输出输出输出：算法产生至少一个量作为输出。：算法产生至少一个量作为输出。(3)(3)确定性确定性确定性确定性：组成算法的每条指令是清晰，无歧义的。：组成算法的每条指令是清晰，无歧义的。(4)(4)有限性有限性有限性有限性：算法中每条指令的执行次数是有限的，执行每：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。条指令的时间也是有限的。本讲稿第六页，共四十二页程序程序程序程序(Program)(Program)程序是算法用某

5、种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质程序可以不满足算法的性质(4)(4)。例如操作系统，是一个在无限循环中执行的程序，因而不是一个例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。算法。操作系统的各种任务可看成是单独的问题，每一个问题由操操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。到输出结果后便终止。本讲稿第七页，共四十二页问题求解问题求解问题求解问题求解(Problem Solving)(Prob

6、lem Solving)证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法本讲稿第八页，共四十二页算法复杂性分析算法复杂性分析 算法复杂性算法复杂性 =算法所需要的计算机资源算法所需要的计算机资源算法的时间复杂性算法的时间复杂性T T(n n)；算法的空间复杂性算法的空间复杂性S S(n n)。其中其中n n是问题的规模（输入大小）。是问题的规模（输入大小）。本讲稿第九页，共四十二页算法的时间复杂性算法的时间复杂性算法的时间复杂性算法的时间复杂性（1 1）最坏情况最坏情况最坏情况最坏情况下的时间复杂性下的时间复杂性 T Tmaxmax(n n)=max)=max

7、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是问题的规模为是问题的规模为n n的实例，的实例，p p(I)(I)是实是实 例例I I出现的概率。出现的概率。本讲稿第十页，共四十二页算法渐近复杂性算法渐近复杂性算法渐近复杂性算法渐近复杂性T T(n n),as ,as n n;(T

8、 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)简单。简单。本讲稿第十一页，共四十二页渐近分析的记号渐近分析的记号在下面的讨论中，对所有在下面的讨论中，对所有n n，f f(n n)0 0，g g(n n)0 0。（1 1）渐近上界记号渐近上界记号渐近上界记号渐近上界记号OOOO(g g

9、(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有：有：0 0 cgcg(n n)f f(n n)本讲稿第十二页，共四十二页（3 3）非紧上界记号非紧上界记号非紧上界记号非紧上界记号o o o o(g g(n n)=)=f f(n n)|)|对于任何正常数对于任何正常数c c00，存在正数

10、和存在正数和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)o o(f f(n n)本讲稿第十三页，共四十二页（5 5）紧渐近界记号紧渐近界记号紧渐近界记号紧渐近界记号 (g g(n n)=)=f f(n n)|)|存在正常数存在正常数c c1 1,c,c2 2和和n n0 0使得对所有使得对所有n

11、 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)本讲稿第十四页，共四十二页渐近分析记号在等式和不等式中的意义渐近分析记号在等式和不等式中的意义f f(n 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

12、+(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,和和 的意义是类似的。的意义是类似的。本讲稿第十五页，共四十二页渐近分析中函数比较渐近分析中函数比较渐近分析中函数比较渐近分析中函数比较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.

13、本讲稿第十六页，共四十二页渐近分析记号的若干性质渐近分析记号的若干性质渐近分析记号的若干性质渐近分析记号的若干性质（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 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

14、 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）反身性：）反身性：）反身性：）反身性：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）互对称性：）互对称性：）互对称性：）

15、互对称性：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 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)=

16、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)。本讲稿第十九页，共四十二页规则规则OO(f f(n n)+)+OO(g g(n n)=OO(max(maxf f(n),(n),g g(n n)的的证明：证明：证明：证明：对于任意对于任意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

17、)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 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

18、 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).).本讲稿第二十页，共四十二页算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数算法渐近复杂性分析中常用函数（1 1）单调函数）单调函数）单调函数）单调函数单调递增：单调递增：mm n n f f(mm)f f(n n);单调递减：单调递减：mm n n f f(mm)f f(n n););严格单调递增：严格单调递增：mm n

19、 n f f(mm)f f(n n););严格单调递减：严格单调递减：mm )f f(n n).).（2 2）取整函数）取整函数）取整函数）取整函数 x x ：不大于：不大于x x的最大整数；的最大整数；x x ：不小于：不小于x x的最小整数。的最小整数。本讲稿第二十一页，共四十二页取整函数的若干性质取整函数的若干性质取整函数的若干性质取整函数的若干性质 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

20、a-(-(b b-1)/-1)/b b;f f(x x)=)=x x ,g g(x x)=)=x x 为为单调递增函数。单调递增函数。本讲稿第二十二页，共四十二页（3 3）多项式函数）多项式函数）多项式函数）多项式函数 p p(n n)=)=a a0 0+a a1 1n n+a a2 2n n2 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););

21、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 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)本讲稿第二十四页，共四十二页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

22、ex x =1+=1+x+x+(x x2 2),as),as x x0;0;本讲稿第二十五页，共四十二页（5 5）对数函数）对数函数）对数函数）对数函数 log log n n=log=log2 2n n;lg lg n n=log=log1010n n;ln ln n n=log=loge en 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本讲稿第二十六页，共四十二页本讲稿第二十七页，共四十二页|x|x|1 1 for for x

23、 x -1,-1,for any for any a a 0,0,log logb bn n=o o(n na a)本讲稿第二十八页，共四十二页（6 6）阶层函数）阶层函数）阶层函数）阶层函数Stirlings approximationStirlings approximation 本讲稿第二十九页，共四十二页本讲稿第三十页，共四十二页算法分析中常见的复杂性函数算法分析中常见的复杂性函数本讲稿第三十一页，共四十二页小规模数据小规模数据本讲稿第三十二页，共四十二页中等规模数据中等规模数据本讲稿第三十三页，共四十二页执行时间随执行时间随执行时间随执行时间随n n的增长而增长的情况的增长而增长的情

24、况 n n!n!n n!n!n n!n!n n!n!5120s9362ms131.72h1711.27year6720s103.62s1424h18203year75.04ms1139.9s1515day193857year840.3ms12479.0s16242day2077146year1.多项式时间复杂度算法多项式时间复杂度算法多项式时间复杂度算法多项式时间复杂度算法 p类问题类问题类问题类问题 2.指数时间复杂度算法指数时间复杂度算法指数时间复杂度算法指数时间复杂度算法 n!或者或者或者或者2exp(n)NPNP类问题类问题类问题类问题本讲稿第三十四页，共四十二页算法分析方法算法分析方

25、法算法分析方法算法分析方法例：顺序搜索算法例：顺序搜索算法例：顺序搜索算法例：顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;本讲稿第三十五页，共四十二页（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）在平均情况下，假设：）在平均情

26、况下，假设：(a)(a)搜索成功的概率为搜索成功的概率为p p(0(0 p p 1)1)；(b)(b)在数组的每个位置在数组的每个位置i i(0(0 i i n n)搜索成功的概率相同，均为搜索成功的概率相同，均为 p p/n n。本讲稿第三十六页，共四十二页算法分析的基本法则算法分析的基本法则非递归算法：非递归算法：非递归算法：非递归算法：（1 1）for/while for/while 循环循环循环体内计算时间循环体内计算时间*循环次数；循环次数；（2 2）嵌套循环）嵌套循环循环体内计算时间循环体内计算时间*所有循环次数；所有循环次数；（3 3）顺序语句）顺序语句各语句计算时间相加；各语句

27、计算时间相加；（4 4）if-elseif-else语句语句if if语句计算时间和语句计算时间和elseelse语句计算时间的较大者。语句计算时间的较大者。本讲稿第三十七页，共四十二页templatevoid insertion_sort(Type*a,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 本讲稿第三十八页，共四十二页在最好情况下，在最好情况下，t ti i=1,for 1=1,for

28、1 i i n n;在最坏情况下，在最坏情况下，t ti i i i+1,for 1+1,for 1 i i n n;本讲稿第三十九页，共四十二页对于输入数据对于输入数据ai=n-i,i=0,1,n-1ai=n-i,i=0,1,n-1，算法，算法insertion_sort insertion_sort 达到其最坏情形。因达到其最坏情形。因此，此，由此可见，由此可见，T Tmaxmax(n n)=)=(n n2 2)本讲稿第四十页，共四十二页最优算法最优算法最优算法最优算法问题的计算时间下界为问题的计算时间下界为(f f(n n)，则计算时间复杂性为，则计算时间复杂性为O(O(f f(n n)

29、的算法是最优算法。的算法是最优算法。例如，排序问题的计算时间下界为例如，排序问题的计算时间下界为(n nloglogn n)，计算时间复杂性为，计算时间复杂性为OO(n nloglogn n)的的排序算法是最优算法。排序算法是最优算法。堆排序算法是最优算法。堆排序算法是最优算法。本讲稿第四十一页，共四十二页递归算法复杂性分析递归算法复杂性分析 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);本讲稿第四十二页，共四十二页