王晓东电子计算机算法设计与分析第学习教案.pptx

《王晓东电子计算机算法设计与分析第学习教案.pptx》由会员分享，可在线阅读，更多相关《王晓东电子计算机算法设计与分析第学习教案.pptx（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1王晓东电子计算机算法王晓东电子计算机算法(sun f)设计与分析设计与分析第第第一页，共51页。算法算法算法算法(sun f(sun f)(Algorithm)(Algorithm)n n算法是指解决问题的一种方法或一个过程。算法是指解决问题的一种方法或一个过程。n n算法是若干指令的有穷序列，满足算法是若干指令的有穷序列，满足(m(m nz)nz)性质：性质：n n(1)(1)输入：有外部提供的量作为算法的输入。输入：有外部提供的量作为算法的输入。n n(2)(2)输出：算法产生至少一个量作为输出。输出：算法产生至少一个量作为输出。n n(3)(3)确定性：组成算法的每条指令是清晰，

2、无歧义的。确定性：组成算法的每条指令是清晰，无歧义的。n n(4)(4)有限性：算法中每条指令的执行次数是有限的，执行有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。每条指令的时间也是有限的。第2页/共51页第二页，共51页。程序程序程序程序(chngx)(Program)(chngx)(Program)n n程序是算法用某种程序设计语言的具体实现。程序是算法用某种程序设计语言的具体实现。n n程序可以不满足算法的性质程序可以不满足算法的性质(4)(4)。n n例如操作系统，是一个在无限循环中执行的程序，因而不例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法

3、。是一个算法。n n操作系统的各种任务可看成是单独的问题，每一个问题由操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过操作系统中的一个子程序通过(tnggu)(tnggu)特定的算法来实现。特定的算法来实现。该子程序得到输出结果后便终止。该子程序得到输出结果后便终止。第3页/共51页第三页，共51页。问题问题问题问题(wnt)(wnt)求解求解求解求解(Problem Solving)(Problem Solving)理解(lji)问题精确(jngqu)解或近似解选择数据结构算法设计策略设计算法第4页/共51页第四页，共51页。算法算法算法算法(sun f(sun

4、f)复杂性分析复杂性分析复杂性分析复杂性分析 n n算法复杂性算法复杂性=算法所需要的计算机资源算法所需要的计算机资源(zyun)(zyun)n n算法的时间复杂性算法的时间复杂性T(n)T(n)；n n算法的空间复杂性算法的空间复杂性S(n)S(n)。n n其中其中n n是问题的规模（输入大小）。是问题的规模（输入大小）。第5页/共51页第五页，共51页。算法算法算法算法(sun f(sun f)的时间复杂性的时间复杂性的时间复杂性的时间复杂性n n（1 1）最坏情况下的时间复杂性）最坏情况下的时间复杂性n n Tmax(n)=max T(I)|size(I)=n Tmax(n)=max T

5、(I)|size(I)=n n n（2 2）最好）最好(zu h(zu h o)o)情况下的时间复杂性情况下的时间复杂性n n Tmin(n)=min T(I)|size(I)=n Tmin(n)=min T(I)|size(I)=n n n（3 3）平均情况下的时间复杂性）平均情况下的时间复杂性n n Tavg(n)=Tavg(n)=n n 其中其中I I是问题的规模为是问题的规模为n n的实例，的实例，p(I)p(I)是实是实 例例I I出现的概率。出现的概率。第6页/共51页第六页，共51页。算法算法算法算法(sun f(sun f)渐近复杂性渐近复杂性渐近复杂性渐近复杂性n nT(n)

6、T(n),as n,as n;n n(T(n)-t(n)/T(n)(T(n)-t(n)/T(n)0 0，as nas n;n nt(n)t(n)是是T(n)T(n)的渐近性态，为算法的渐近复杂性。的渐近性态，为算法的渐近复杂性。n n在数学上，在数学上，t(n)t(n)是是T(n)T(n)的渐近表达式，是的渐近表达式，是T(n)T(n)略去低阶项留下略去低阶项留下的主项的主项(zh(zh xin xin)。它比。它比T(n)T(n)简单。简单。第7页/共51页第七页，共51页。渐近分析渐近分析渐近分析渐近分析(fnx)(fnx)的记号的记号的记号的记号n n在下面在下面(xi mian)(xi

7、 mian)的讨论中，对所有的讨论中，对所有n n，f(n)f(n)0 0，g(n)g(n)0 0。n n（1 1）渐近上界记号）渐近上界记号OOn nO(g(n)=f(n)|O(g(n)=f(n)|存在正常数存在正常数c c和和n0n0使得对所有使得对所有n n n0 n0有：有：0 0 f(n)f(n)cg(n)cg(n)n n（2 2）渐近下界记号）渐近下界记号 n n (g(n)=f(n)|(g(n)=f(n)|存在正常数存在正常数c c和和n0n0使得对所有使得对所有n n n0 n0有：有：0 0 cg(n)cg(n)f(n)f(n)第8页/共51页第八页，共51页。n n（3 3

8、）非紧上界记号）非紧上界记号(j h(j h o)o o)o n no(g(n)=f(n)|o(g(n)=f(n)|对于任何正常数对于任何正常数c0c0，存在正数和，存在正数和n0 0n0 0使得对使得对所有所有n n n0 n0有：有：0 0 f(n)cg(n)f(n)0c0，存在正数和，存在正数和n0 0n0 0使得使得对所有对所有n n n0 n0有：有：0 0 cg(n)f(n)cg(n)f(n)n n等价于等价于 f(n)/g(n)f(n)/g(n)，as nas n。n nf(n)f(n)(g(n)(g(n)g(n)g(n)o(f(n)o(f(n)第9页/共51页第九页，共51页。

9、n n（5 5）紧渐近界记号）紧渐近界记号 n n(g(n)=f(n)|(g(n)=f(n)|存在存在(cnzi)(cnzi)正常数正常数c1,c2c1,c2和和n0n0使得对所使得对所有有n n n0 n0有：有：c1g(n)c1g(n)f(n)f(n)c2g(n)c2g(n)n n 定理定理1 1：(g(n)=O(g(n)(g(n)=O(g(n)(g(n)(g(n)第10页/共51页第十页，共51页。渐近分析记号在等式渐近分析记号在等式渐近分析记号在等式渐近分析记号在等式(dngsh)(dngsh)和不等式和不等式和不等式和不等式(dngsh)(dngsh)中的意义中的意义中的意义中的意义

10、n nf(n)=f(n)=(g(n)(g(n)的确切意义是：的确切意义是：f(n)f(n)(g(n)(g(n)。n n一般情况下，等式一般情况下，等式(dngsh)(dngsh)和不等式和不等式(dngsh)(dngsh)中的渐近记号中的渐近记号(g(n)(g(n)表示表示(g(n)(g(n)中的某个中的某个函数。函数。n n例如：例如：2n2+3n+1=2n2+2n2+3n+1=2n2+(n)(n)表示表示n n 2n2+3n+1=2n2+f(n)2n2+3n+1=2n2+f(n)，其中，其中f(n)f(n)是是(n)(n)中某个函数。中某个函数。n n等式等式(dngsh)(dngsh)和

11、不等式和不等式(dngsh)(dngsh)中渐近记号中渐近记号O,o,O,o,和和的意义是类似的。的意义是类似的。第11页/共51页第十一页，共51页。渐近分析渐近分析渐近分析渐近分析(fnx)(fnx)中函数比较中函数比较中函数比较中函数比较n nf f(n n)=)=O O(g g(n n)a a b;b;n nf f(n n)=)=(g g(n n)a a b;b;n nf f(n n)=)=(g g(n n)a a=b;=b;n nf f(n n)=)=o o(g g(n n)a a b;b.b.第12页/共51页第十二页，共51页。渐近分析记号渐近分析记号渐近分析记号渐近分析记号(j

12、 h(j h o)o)的若干性质的若干性质的若干性质的若干性质n n（1 1）传递性：）传递性：）传递性：）传递性：n nf f(n n)=)=(g g(n n)，g g(n n)=)=(h h(n n)f f(n n)=)=(h h(n n)；n nf 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)；n nf f(n n)=)=(g g(n n)，g g(n n)=)=(h h(n n)f f(n n)=)=(h h(n n)；n nf f(n n)=)=o o(g g(n n)，g g(n n)=

13、)=o o(h h(n n)f f(n n)=)=o o(h h(n n)；n nf f(n n)=)=(g g(n n)，g g(n n)=)=(h h(n n)f f(n n)=)=(h h(n n)；第13页/共51页第十三页，共51页。n n（2 2）反身）反身）反身）反身(f(f n shn)n shn)性：性：性：性：n nf(n)=f(n)=(f(n)(f(n)；n nf(n)=O(f(n)f(n)=O(f(n)；n nf(n)=f(n)=(f(n).(f(n).n n（3 3）对称性：）对称性：）对称性：）对称性：n nf(n)=f(n)=(g(n)(g(n)g(n)=g(n)

14、=(f(n).(f(n).n n（4 4）互对称性：）互对称性：）互对称性：）互对称性：n nf(n)=O(g(n)f(n)=O(g(n)g(n)=g(n)=(f(n)(f(n)；n nf(n)=o(g(n)f(n)=o(g(n)g(n)=g(n)=(f(n)(f(n)；第14页/共51页第十四页，共51页。n n（5 5）算术）算术）算术）算术(sunsh)(sunsh)运算：运算：运算：运算：n nO(f(n)+O(g(n)=O(maxf(n),g(n)O(f(n)+O(g(n)=O(maxf(n),g(n)；n nO(f(n)+O(g(n)=O(f(n)+g(n)O(f(n)+O(g(n

15、)=O(f(n)+g(n)；n nO(f(n)*O(g(n)=O(f(n)*g(n)O(f(n)*O(g(n)=O(f(n)*g(n)；n nO(cf(n)=O(f(n)O(cf(n)=O(f(n)；n ng(n)=O(f(n)g(n)=O(f(n)O(f(n)+O(g(n)=O(f(n)O(f(n)+O(g(n)=O(f(n)。第15页/共51页第十五页，共51页。n n规则规则(guz)O(f(n)+O(g(n)=O(maxf(n),g(n)(guz)O(f(n)+O(g(n)=O(maxf(n),g(n)的证明：的证明：n n对于任意对于任意f1(n)f1(n)O(f(n)O(f(n)，

16、存在正常数，存在正常数c1c1和自然数和自然数n1n1，使得对所有，使得对所有n n n1 n1，有，有f1(n)f1(n)c1f(n)c1f(n)。n n类似地，对于任意类似地，对于任意g1(n)g1(n)O(g(n)O(g(n)，存在正常数，存在正常数c2c2和自然数和自然数n2n2，使得对所，使得对所有有n n n2 n2，有，有g1(n)g1(n)c2g(n)c2g(n)。n n令令c3=maxc1,c2c3=maxc1,c2，n3=maxn1,n2 n3=maxn1,n2，h(n)=maxf(n),g(n)h(n)=maxf(n),g(n)。n n则对所有的则对所有的 n n n3

17、n3，有，有n nf1(n)+g1(n)f1(n)+g1(n)c1f(n)+c2g(n)c1f(n)+c2g(n)n n c3f(n)+c3g(n)=c3(f(n)+g(n)c3f(n)+c3g(n)=c3(f(n)+g(n)n n c32 maxf(n),g(n)c32 maxf(n),g(n)n n =2c3h(n)=O(maxf(n),g(n).=2c3h(n)=O(maxf(n),g(n).第16页/共51页第十六页，共51页。算法算法算法算法(sun f(sun f)渐近复杂性分析中常用函数渐近复杂性分析中常用函数渐近复杂性分析中常用函数渐近复杂性分析中常用函数n n（1 1）单调函

18、数）单调函数）单调函数）单调函数(hnsh)(hnsh)n n单调递增：单调递增：单调递增：单调递增：m m n n f(m)f(m)f(n);f(n);n n单调递减：单调递减：单调递减：单调递减：m m n n f(m)f(m)f(n);f(n);n n严格单调递增：严格单调递增：严格单调递增：严格单调递增：m n m n f(m)f(n);f(m)f(n);n n严格单调递减：严格单调递减：严格单调递减：严格单调递减：m n m f(n).f(m)f(n).n n（2 2）取整函数）取整函数）取整函数）取整函数(hnsh)(hnsh)n n x x ：不大于：不大于：不大于：不大于x x

19、的最大整数；的最大整数；的最大整数；的最大整数；n n x x ：不小于：不小于：不小于：不小于x x的最小整数。的最小整数。的最小整数。的最小整数。第17页/共51页第十七页，共51页。取整函数的若干取整函数的若干取整函数的若干取整函数的若干(rugn)(rugn)性质性质性质性质n n x-1 x-1 x x x x x x x+1 0a,b0，有：，有：n n n/a n/a /b /b =n/ab n/ab ;n n n/a n/a /b /b =n/ab n/ab ;n n a/b a/b (a+(b-1)/b;(a+(b-1)/b;n n a/b a/b (a-(b-1)/b;(a

20、-(b-1)/b;n n f(x)=f(x)=x x ,g(x)=,g(x)=x x 为单调为单调(dndio)(dndio)递增函数。递增函数。第18页/共51页第十八页，共51页。n n（3 3）多项式函数）多项式函数）多项式函数）多项式函数(hnsh)(hnsh)n n p(n)=a0+a1n+a2n2+adnd p(n)=a0+a1n+a2n2+adnd；ad0;ad0;n n p(n)=p(n)=(nd);(nd);n n f(n)=O(nk)f(n)=O(nk)f(n)f(n)多项式有界；多项式有界；多项式有界；多项式有界；n n f(n)=O(1)f(n)=O(1)f(n)f(n

21、)c;c;n n k k d d p(n)=O(nk);p(n)=O(nk);n nk k d d p(n)=p(n)=(nk);(nk);n nk d k d p(n)=o(nk);p(n)=o(nk);n nk d k 0:a0:n n a0=1;a0=1;n n a1=a;a1=a;n n a-1=1/a;a-1=1/a;n n(am)n=amn;(am)n=amn;n n(am)n=(an)m;(am)n=(an)m;n n aman =am+n;aman =am+n;n n a1 a1 an an为单调递增函数为单调递增函数为单调递增函数为单调递增函数;n n a1 a1 nb=o(

22、an)nb=o(an)第20页/共51页第二十页，共51页。n ne ex x 1+1+x x;n n|x|x|1 1 1+1+x x e ex x 1+1+x+xx+x2 2;n n e ex x =1+=1+x+x+(x x2 2),as),as x x0;0;第21页/共51页第二十一页，共51页。n n（5 5）对数函数）对数函数）对数函数）对数函数(du sh hn sh)(du sh hn sh)n n log n=log2n;log n=log2n;n n lg n=log10n;lg n=log10n;n n ln n=logen;ln n=logen;n n logkn=(l

23、og n)kl;logkn=(log n)kl;n n log log n=log(log n);log log n=log(log n);n n for a0,b0,c0 for a0,b0,c0第22页/共51页第二十二页，共51页。第23页/共51页第二十三页，共51页。n n|x|x|1 1 n nfor for x x -1,-1,n nfor any for any a a 0,0,log logb bn n=o o(n na a)第24页/共51页第二十四页，共51页。n n（6 6）阶层）阶层）阶层）阶层(jicng)(jicng)函数函数函数函数n nStirlings ap

24、proximation Stirlings approximation 第25页/共51页第二十五页，共51页。第26页/共51页第二十六页，共51页。算法分析算法分析算法分析算法分析(fnx)(fnx)中常见的复杂性函数中常见的复杂性函数中常见的复杂性函数中常见的复杂性函数第27页/共51页第二十七页，共51页。小规模数据小规模数据小规模数据小规模数据(shj)(shj)第28页/共51页第二十八页，共51页。中等规模中等规模中等规模中等规模(gum)(gum)数据数据数据数据第29页/共51页第二十九页，共51页。用用用用C+C+描述描述描述描述(mio sh)(mio sh)算法算法算法

25、算法第30页/共51页第三十页，共51页。n n（1 1）选择）选择）选择）选择(xu(xu nz)nz)语句：语句：语句：语句：n n（1.1)if 1.1)if 语句：语句：语句：语句：n n（1.2)1.2)？语句：？语句：？语句：？语句：n n if(expression)statement;else statement;exp1?exp2:exp3 y=x9?100:200;等价(dngji)于：if(x9)y=100;else y=200;第31页/共51页第三十一页，共51页。（1.3)switch1.3)switch语句语句语句语句(y(y j)j)：switch(expres

26、sion)case 1:statement sequence;break;case 2:statement sequence;break;default:statement sequence;第32页/共51页第三十二页，共51页。（2 2）迭代）迭代）迭代）迭代(di di)(di di)语句：语句：语句：语句：n n（2.1)for 2.1)for 循环循环循环循环(xnhun)(xnhun)：n n for(init;condition;inc)statement;for(init;condition;inc)statement;n n（2.2)while 2.2)while 循环循环循

27、环循环(xnhun)(xnhun)：n n while(condition)statement;while(condition)statement;n n（2.3)do-while 2.3)do-while 循环循环循环循环(xnhun)(xnhun)：n n do don n statement;statement;n n while(condition);while(condition);第33页/共51页第三十三页，共51页。（3 3）跳转语句）跳转语句）跳转语句）跳转语句(y(y j)j)：n n（3.1)return3.1)return语句语句语句语句(y(y j)j)：n n re

28、turn expression;return expression;n n（3.2)goto3.2)goto语句语句语句语句(y(y j)j)：n n goto label;goto label;n n n n label:label:第34页/共51页第三十四页，共51页。（4 4）函数）函数）函数）函数(hnsh)(hnsh)：n n例：例：例：例：return-type function name(para-list)body of the function int max(int x,int y)return xy?x:y;第35页/共51页第三十五页，共51页。（5 5）模板）模板）

29、模板）模板(mb(mb n)template n)template：template Type max(Type x,Type y)return xy?x:y;int i=max(1,2)；double x=max(1.0,2.0)；第36页/共51页第三十六页，共51页。（6 6）动态存储分配：）动态存储分配：）动态存储分配：）动态存储分配：n n（6.16.1）运算符）运算符）运算符）运算符new new：n n运算符运算符运算符运算符newnew用于动态存储分配。用于动态存储分配。用于动态存储分配。用于动态存储分配。n nnewnew返回一个指向所分配空间的指针。返回一个指向所分配空间的

30、指针。返回一个指向所分配空间的指针。返回一个指向所分配空间的指针。n n例：例：例：例：int int x x；y=new inty=new int；y=10y=10；n n也可将上述各语句也可将上述各语句也可将上述各语句也可将上述各语句(y(y j)j)作适当合并如下：作适当合并如下：作适当合并如下：作适当合并如下：n nint int y=new inty=new int；y=10y=10；n n或或或或 int int y=new int(10)y=new int(10)；n n或或或或 int int y y；y=new int(10)y=new int(10)；第37页/共51页第三

31、十七页，共51页。（6.26.2）一维数组）一维数组）一维数组）一维数组 ：n n为了在运行时创建一个大小可动态为了在运行时创建一个大小可动态(dngti)(dngti)变化的一维浮点数组变化的一维浮点数组x x，可先将，可先将x x声明为一个声明为一个floatfloat类型的指针。然后用类型的指针。然后用newnew为数组动态为数组动态(dngti)(dngti)地分配存储空间。地分配存储空间。n n例：例：n nfloat float x=new floatnx=new floatn；n n创建一个大小为创建一个大小为n n的一维浮点数组。运算符的一维浮点数组。运算符newnew分配分配

32、n n个浮点数所需的个浮点数所需的空间，并返回指向第一个浮点数的指针。空间，并返回指向第一个浮点数的指针。n n然后可用然后可用x0 x0，x1x1，xn-1xn-1来访问每个数组元素。来访问每个数组元素。第38页/共51页第三十八页，共51页。（6.36.3）运算符）运算符）运算符）运算符delete delete：n n当动态分配的存储空间已不再需要时应及时释放所占用当动态分配的存储空间已不再需要时应及时释放所占用(zhn yn(zhn yn)的空间。的空间。n n用运算符用运算符deletedelete来释放由来释放由newnew分配的空间。分配的空间。n n例：例：n ndelete

33、ydelete y；n ndelete xdelete x；n n分别释放分配给分别释放分配给y y的空间和分配给一维数组的空间和分配给一维数组x x的空间。的空间。第39页/共51页第三十九页，共51页。（6.46.4）动态）动态）动态）动态(dngti)(dngti)二维数组二维数组二维数组二维数组 ：n n创建创建(chungjin)(chungjin)类型为类型为TypeType的动态工作数组，这个的动态工作数组，这个数组有数组有rowsrows行和行和colscols列。列。template void Make2DArray(Type*&x,int rows,int cols)x=n

34、ew Type*rows;for(int i=0;irows;i+)xi=new Typecols;第40页/共51页第四十页，共51页。n n当不再需要一个当不再需要一个(y(y )动态分配的二维数组时，可按以下步骤释放它所动态分配的二维数组时，可按以下步骤释放它所占用的空间。首先释放在占用的空间。首先释放在forfor循环中为每一行所分配的空间。然后释放为循环中为每一行所分配的空间。然后释放为行指针分配的空间。行指针分配的空间。n n释放空间后将释放空间后将x x置为置为0 0，以防继续访问已被释放的空间。，以防继续访问已被释放的空间。template void Delete2DArray

35、(Type*&x,int rows)for(int i=0;irows;i+)delete xi;delete x;x=0;第41页/共51页第四十一页，共51页。算法算法算法算法(sun f(sun f)分析方法分析方法分析方法分析方法n n例：顺序例：顺序例：顺序例：顺序(shnx)(shnx)搜索算法搜索算法搜索算法搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;第42页/共51页第四十二页，共51页。n n（1 1）Tmax(n)=max T(I)|siz

36、e(I)=n=O(n)Tmax(n)=max T(I)|size(I)=n=O(n)n n（2 2）Tmin(n)=min T(I)|size(I)=n=O(1)Tmin(n)=min T(I)|size(I)=n=O(1)n n（3 3）在平均情况下，假设：）在平均情况下，假设：n n (a)(a)搜索成功搜索成功(chnggng)(chnggng)的概率为的概率为p(0 p(0 p p 1)1)；n n (b)(b)在数组的每个位置在数组的每个位置i(0 i(0 i n)i n)搜索成功搜索成功(chnggng)(chnggng)的概率相同，均为的概率相同，均为 p/np/n。第43页/共

37、51页第四十三页，共51页。算法分析的基本算法分析的基本算法分析的基本算法分析的基本(jbn)(jbn)法则法则法则法则n n非递归算法：非递归算法：非递归算法：非递归算法：n n（1 1）for/while for/while 循环循环循环循环n n循环体内计算时间循环体内计算时间循环体内计算时间循环体内计算时间*循环次数；循环次数；循环次数；循环次数；n n（2 2）嵌套循环）嵌套循环）嵌套循环）嵌套循环n n循环体内计算时间循环体内计算时间循环体内计算时间循环体内计算时间*所有循环次数；所有循环次数；所有循环次数；所有循环次数；n n（3 3）顺序）顺序）顺序）顺序(shnx)(shnx

38、)语句语句语句语句n n各语句计算时间相加；各语句计算时间相加；各语句计算时间相加；各语句计算时间相加；n n（4 4）if-elseif-else语句语句语句语句n nif if语句计算时间和语句计算时间和语句计算时间和语句计算时间和elseelse语句计算时间的较大者。语句计算时间的较大者。语句计算时间的较大者。语句计算时间的较大者。第44页/共51页第四十四页，共51页。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

39、sum of(ti-1)j-;/c6 sum og(ti-1)aj+1=key;/c7 n-1 第45页/共51页第四十五页，共51页。n n在最好在最好(zu h(zu h o)o)情况下，情况下，ti=1,for 1 ti=1,for 1 i n;i n;n n在最坏情况下，在最坏情况下，ti ti i+1,for 1 i+1,for 1 i n;i n;第46页/共51页第四十六页，共51页。n n对于输入数据对于输入数据ai=n-i,i=0,1,n-1ai=n-i,i=0,1,n-1，算法，算法insertion_sort insertion_sort 达到其最坏情形达到其最坏情形(q

40、ng(qng xing)xing)。因此，。因此，n n由此可见，由此可见，Tmax(n)=Tmax(n)=(n2)(n2)第47页/共51页第四十七页，共51页。最优算法最优算法最优算法最优算法(sun f(sun f)n n问题问题(wnt)(wnt)的计算时间下界为的计算时间下界为(f(n)(f(n)，则计算时间复杂性为，则计算时间复杂性为O(f(n)O(f(n)的算法是最优算法。的算法是最优算法。n n例如，排序问题例如，排序问题(wnt)(wnt)的计算时间下界为的计算时间下界为(nlogn)(nlogn)，计算时间复杂性为，计算时间复杂性为O(nlogn)O(nlogn)的排序算法

41、是最优算法。的排序算法是最优算法。n n堆排序算法是最优算法。堆排序算法是最优算法。第48页/共51页第四十八页，共51页。递归算法递归算法递归算法递归算法(sun f(sun f)复杂性分析复杂性分析复杂性分析复杂性分析n n int int factorialfactorial(int n)(int n)n n n n if(n=0)return 1;if(n=0)return 1;n n return n*factorial(n-1);return n*factorial(n-1);n n 第49页/共51页第四十九页，共51页。第50页/共51页第五十页，共51页。感谢您的观看感谢您的观看(gunkn)！第51页/共51页第五十一页，共51页。