2-算法效率分析基础.pptx
2-算法效率分析基础算法效率分析基础陆伟College of Software and Microelectronics算法设计与分析算法设计与分析Introduction to the Design and Analysis of Algorithms 29 April 2022Northwestern Polytechnical UniversityLecture Overview1. 算法效率的度量 2. 函数的渐进的界3. 算法的基本复杂性类型4. 算法复杂性分析的基本方法5. 非递归算法的复杂性分析6. 递归算法的复杂性分析7. 递归算法与非递归算法比较8. 经验分析方法9. 算法可视化2算法效率的度量算法效率的度量 算法效率的高低体现在运行该算法所需要耗费资源的多少，对于计算机来讲，最重要的资源是时间和空间，因此，算法效率又可分为时间效率和空间效率。 分别用N，I和A表示要解决问题的规模、算法的输入和算法本身，用C表示复杂性，那么，应该有C = F(N, I, A)。如果吧时间复杂性与空间复杂性分开，分别用T和S表示，则T = F(N, I, A)，S = F(N, I, A)。 T = T(N, I)，S = S(N, I)。3算法效率的度量算法效率的度量 计算机存储容量的发展使得算法空间复杂性已经不再是关注的重点，但时间复杂性仍然十分重要。因此，我们后续也将主要讨论算法的时间复杂性，但是所讨论的方法对于空间复杂性分析也是适用的。 根据T = T(N, I)的概念，它应该是算法在一台“抽象的计算机”上运行所需要的时间。4算法效率的度量算法效率的度量 设该“抽象的计算机”所提供的元运算有k种，分别记为O1,O2,Ok，又设每执行一次这些元运算所耗费的时间分别为t1,t2,tk。对于给定算法A，统计其执行过程中用到的元运算Oi的次数，记为ei，i=1,2,k。ei = ei (N, I)。 其中，ti是与N和I无关的常数。51()(, )kiiiT N,It e N I算法效率的度量算法效率的度量 我们不可能对规模为N的每一种合法输入I都去统计ei(N, I)，i=1,2,k。 关于摊销效率6max11()max (, )max(, )(, *)NNkkiiiiI DI DiiTNT N It e N It e N Imin11()min (, )min(, )(, )NNkkiiiiI DI DiiTNT N It e N It e N Iavg11()( ) (, )( )(, )(, )NNkkiiiiI DI DiiTNP I T N IP It e N It e N I 函数的渐进的界函数的渐进的界 函数的渐进的界 设f 和g 是定义域为自然数集N上的函数(1) f(n)=O(g(n)若存在正数c和n0使得对一切nn0有0f(n)cg(n)(2) f(n)= (g(n)若存在正数c和n0使得对一切nn0有0cg(n) f(n)(3) f(n)=o(g(n)对任意正数c存在n0使得对一切nn0有0f(n)cg(n)(4) f(n)=(g(n)对任意正数c存在n0使得对一切nn0有0cg(n)1和0，logbn=o(n)，n=o(bn)。 n!=o(nn)，n!= (2n)，log(n!)= (nlogn)122log()non算法的基本复杂性类型算法的基本复杂性类型13算法复杂性分析的基本方法算法复杂性分析的基本方法（1）决定表示输入规模的参数。（2）找出算法的基本操作。（3）检查基本操作的执行次数是否只依赖于输入规模。如果还依赖于输入的其它特性，考虑最差、平均以及最优情况下的复杂性。（4）对于非递归算法，建立算法基本操作执行次数的求和表达式；对于递归算法，建立算法基本操作执行次数的递推关系及其初始条件。（5）利用求和公式和法则建立一个操作次数的闭合公式，或者求解递推关系式，确定增长的阶。14非递归算法的复杂性分析非递归算法的复杂性分析 对于等差数列ak， 对于等比数列aqk， 对于调和级数1/k， 对数求和，15 1nkka0nkkaq11nkk1lognii非递归算法的复杂性分析非递归算法的复杂性分析 例16算法算法 MaxElement(A0.n-1/求给定数组中的最大元素/输入：实数数组A0.n-1/输出：A中的最大元素maxval A0for i 1 to n-1 do if Ai maxval maxval Aireturn maxval非递归算法的复杂性分析非递归算法的复杂性分析（1）算法输入规模：可以用数组元素个数n度量（2）基本操作：比较与赋值两种，选择比较（3）比较操作只与输入规模相关，不用考虑最坏、平均、最好情况（4）建立基本操作执行次数求和表达式（5）确定增长的阶17非递归算法的复杂性分析非递归算法的复杂性分析18算法算法 UniqueElements(A0.n-1/验证给定数组中的元素是否全部唯一/输入：实数数组A0.n-1/输出：如果A中的元素全部唯一，返回“true”，否则，返回“false”for i1 to n-2 do for ji +1 to n-1 do if Ai = Aj return falsereturn true非递归算法的复杂性分析非递归算法的复杂性分析19templatevoid 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 of (ti-1) aj+1=key; / c7 n-1 非递归算法的复杂性分析非递归算法的复杂性分析20) 1() 1() 1() 1() 1()(7116115114321nctctctcncncncnTniiniinii在最好情况下，ti=1, for 1 i n;在最坏情况下，ti i+1, for 1 i 1OnT naT nf nnT(n)=an-1 T(1)+-2( )nn iiaf i（1）若取a=2，f(n)=O(1)，汉诺塔问题 T(n)=O(2n-1)（2）若取a=1，f(n)=n-1，插入排序最坏情况 T(n)= O(n2)递归算法的复杂性分析递归算法的复杂性分析22(1)=1( )()+ ( )1OnT nnaTf nnbT(n)=log-1log0(1)()bbnajjjnnTa fb（1）若 ，0，（2）若 ， （3）若 ， 0，log-( )= ()baf nO nlog( )= ()baT nnlog( )(log )baT nnn log( )= ()baf nnlog+( )= ()baf nn( )( ( )T nf n 递归算法的复杂性分析递归算法的复杂性分析 当f(n)为常数时 当f(n) = cn时231)(log1)()(loganOanOnTablog( )( )( log )()baO nabT nO nnabO nab递归算法的复杂性分析递归算法的复杂性分析 例24int hanoi(int n, int a, int b, int c) if (n = 1) move(a, c); else hanoi(n-1, a, c, b); move(a, c); hanoi(n-1, b, a, c); 递归算法的复杂性分析递归算法的复杂性分析 T(n)= T(n/3)+ T(2n/3)+n2501( )2 ( / 2)-11nT nT nnn递归算法与非递归算法比较递归算法与非递归算法比较 阶乘问题2610!(1)!0nnn nn递归算法与非递归算法比较递归算法与非递归算法比较27int factorial(int n) if(n=0) return 1; return n*factorial(n-1);int factorial(int n) int fn=1; for(int i=2; i=n; i+) fn=fn*i; return fn;递归算法与非递归算法比较递归算法与非递归算法比较 Fibonacci数列2800( )11(1)(2)1nF nnF nF nn边界条件边界条件递归方程递归方程int fibonacci(int n) if (n = 1) return n; return fibonacci(n-1)+fibonacci(n-2);递归算法与非递归算法比较递归算法与非递归算法比较29递归算法与非递归算法比较递归算法与非递归算法比较30static int Fibonacci2(int n) int a = new intn; a0 = 1; a1 = 1; for (int i = 2; i n; i+) ai = ai - 1 + ai - 2; return an - 1;递归算法与非递归算法比较递归算法与非递归算法比较311151151( )()22555nnnnF n(15)/ 21.618031/0.61803 (1)( )01( )(1)11nF nF nF nF n递归算法与非递归算法比较递归算法与非递归算法比较32并非所有递归算法都有非递归定义。 Ackerman函数 Ackerman函数A(n, m)有两个独立的整型变量m0和 n0，定义如下：1,20) 1), 1(),(2)0 ,(1), 0(2)0 , 1 (mnnmmmnAAmnAnnAmAA当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。递归算法与非递归算法比较递归算法与非递归算法比较 Ackerman函数33A(n，m)的自变量m的每一个值都定义了一个单变量函数：m=0时，A(n,0)=n+2m=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，A(1,1)=2故A(n,1)=2nm=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2n。m=3时，类似的可以推出A(n,3)=m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。n2222经验分析法经验分析法 数学远远不是万能的，即使许多貌似简单的算法，有时也很难用数学的精确性和严格性来分析，尤其是在做平均效率分析的时候。 除了可以对算法的效率做数学分析以外，另一种主要方法是对算法的效率做实验和经验分析。34经验分析法经验分析法35算法可视化算法可视化 参考36Summary9、静夜四无邻，荒居旧业贫。22.4.2922.4.29Friday, April 29, 202210、雨中黄叶树，灯下白头人。21:45:5021:45:5021:454/29/2022 9:45:50 PM11、以我独沈久，愧君相见频。22.4.2921:45:5021:45Apr-2229-Apr-2212、故人江海别，几度隔山川。21:45:5021:45:5021:45Friday, April 29, 202213、乍见翻疑梦，相悲各问年。22.4.2922.4.2921:45:5021:45:50April 29, 202214、他乡生白发，旧国见青山。2022年4月29日星期五下午9时45分50秒21:45:5022.4.2915、比不了得就不比，得不到的就不要。2022年4月下午9时45分22.4.2921:45April 29, 202216、行动出成果，工作出财富。2022年4月29日星期五21时45分50秒21:45:5029 April 202217、做前，能够环视四周；做时，你只能或者最好沿着以脚为起点的射线向前。下午9时45分50秒下午9时45分21:45:5022.4.299、没有失败，只有暂时停止成功！。22.4.2922.4.29Friday, April 29, 202210、很多事情努力了未必有结果，但是不努力却什么改变也没有。21:45:5021:45:5021:454/29/2022 9:45:50 PM11、成功就是日复一日那一点点小小努力的积累。22.4.2921:45:5021:45Apr-2229-Apr-2212、世间成事，不求其绝对圆满，留一份不足，可得无限完美。21:45:5021:45:5021:45Friday, April 29, 202213、不知香积寺，数里入云峰。22.4.2922.4.2921:45:5021:45:50April 29, 202214、意志坚强的人能把世界放在手中像泥块一样任意揉捏。2022年4月29日星期五下午9时45分50秒21:45:5022.4.2915、楚塞三湘接，荆门九派通。2022年4月下午9时45分22.4.2921:45April 29, 202216、少年十五二十时，步行夺得胡马骑。2022年4月29日星期五21时45分50秒21:45:5029 April 202217、空山新雨后，天气晚来秋。下午9时45分50秒下午9时45分21:45:5022.4.299、杨柳散和风，青山澹吾虑。22.4.2922.4.29Friday, April 29, 202210、阅读一切好书如同和过去最杰出的人谈话。21:45:5021:45:5021:454/29/2022 9:45:50 PM11、越是没有本领的就越加自命不凡。22.4.2921:45:5021:45Apr-2229-Apr-2212、越是无能的人，越喜欢挑剔别人的错儿。21:45:5021:45:5021:45Friday, April 29, 202213、知人者智，自知者明。胜人者有力，自胜者强。22.4.2922.4.2921:45:5021:45:50April 29, 202214、意志坚强的人能把世界放在手中像泥块一样任意揉捏。2022年4月29日星期五下午9时45分50秒21:45:5022.4.2915、最具挑战性的挑战莫过于提升自我。2022年4月下午9时45分22.4.2921:45April 29, 202216、业余生活要有意义，不要越轨。2022年4月29日星期五21时45分50秒21:45:5029 April 202217、一个人即使已登上顶峰，也仍要自强不息。下午9时45分50秒下午9时45分21:45:5022.4.29MOMODA POWERPOINTLorem ipsum dolor sit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis amet, consectetur adipiscing elit. Fusce id urna blanditut cursus. 感 谢 您 的 下 载 观 看感 谢 您 的 下 载 观 看专家告诉
