第2章-算法的分析基础分析解析.ppt

《第2章-算法的分析基础分析解析.ppt》由会员分享，可在线阅读，更多相关《第2章-算法的分析基础分析解析.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 算法分析基础柯昌博 日期：2015-2-62015-2-6南京邮电大学计算机学院计科系3/3/20232.1 算法复杂度好算法的4个重要特征：Correctness正确性注意区分“正确性”和“健壮性”的概念：算法正确性在合法的输入下，算法应实现预先规定的功能和计算精度要求。程序健壮性当输入不合法的数据时，程序应能做适当处理而不至于引起严重后果。正确性和健壮性互相补充。程序可靠性在正常情况下能正确地工作，在异常情况下也能做出适当处理。2.1 算法复杂度好算法的4个重要特征：Correctness正确性Simplicity,clarity简明性遗憾的是，简单的算法不一定高效思路清晰、层次分

2、明、容易理解、利于编码和调试。2.1 算法复杂度好算法的4个重要特征：Correctness正确性Simplicity,clarity简明性Amount of time/space used效率执行算法所需的时间和存储空间执行算法所需的时间和存储空间算法设计者常常需要在算法的算法设计者常常需要在算法的简明性简明性和和效率效率之间作出谨慎的选择之间作出谨慎的选择2.1 算法复杂度好算法的4个重要特征：Correctness正确性Simplicity,clarity简明性Amount of time/space used效率Optimality最优性算法执行时间达到求解该类问题所算法执行时间达到求

3、解该类问题所需需时间的下界时间的下界。与所求解问题自身的复杂程度有关与所求解问题自身的复杂程度有关。又如：可证排序问题的时间复杂度下界为(nlogn)。则最坏时间复杂性为O(nlogn)的排序算法是最优算法。因此：堆排序算法和两路合并排序算法都是最优算法。例如:FindMax(int L)/求n个元素中的最大元素 int max=L0;int i=1;while(in)if (maxLi)max=Li;i=i+1;最优算法影响程序运行时间的因素程序所依赖的算法问题规模和输入数据计算机系统性能根本的、起决定作用的根本的、起决定作用的数值大小和状态数值大小和状态硬件系统性能（硬件系统性能（CPU速

4、度）和软件系统性能（操作系统、编译器速度）和软件系统性能（操作系统、编译器）输入、输出输入、输出运行一个算法所需的时间和空间资源的量。u算法的时间复杂性（Time Complexity）T(n)u算法的空间复杂性（Space Complexity）S(n)其中n是问题的规模（输入大小）算法复杂度How to Measure?Machine independentLanguage independentProgramming style independentImplementation independent算法的时间复杂度算法的时间复杂度算法运行所需的时间最好、最坏和平均时间复杂度(不考虑计

5、算机因素对算法分析的影响）最好情况（出现概率较大时分析）最差情况（实时系统）平均情况（已知输入数据是如何分布的，通常假设等概率分布）算法的时间复杂度（1）最好情况下的时间复杂性：B(n)=Tmin(n)=min T(n,I)|IDn（2）最坏情况下的时间复杂性：W(n)=Tmax(n)=max T(n,I)|IDn（3）平均情况下的时间复杂性：A(n)=Tavg(n)=I:问题规模为n的实例。Dn:规模为n的所有合法输入的集合。p(I):实例I出现的概率。算法的空间复杂度算法的空间复杂度 算法运行所需的存储空间固定空间需求与所处理数据的大小和个数无关，即与问题实例的特征无关。（包括：程序代码、

6、常量、简单变量、定长成分的结构变量所占的空间）可变空间需求与算法执行过程中处理的特定数据的规模有关。（如：数据元素所占的空间，算法执行所需的额外空间如递归算法所需系统栈空间）通过程序步来分析算法的时间复杂度求数组元素累加之和的迭代程序：(P20 程序2-1)float Sum(float list,const int n)float tempsum=0.0;/1 for(int i=0;i0，则f(n)=O(nm)。例如：程序2-1float Sum(float list,const int n)float tempsum=0.0;/1 for(int i=0;in;i+)/n+1 temps

7、um+=listi;/n return tempsum;/1可以通过考察一个程序中关键操作（key operation）的执行次数，来估算算法的渐近时间复杂度。关键操作！执行次数执行次数n和总的程序步和总的程序步2n+3有有相同的渐近时间复杂度相同的渐近时间复杂度O(n)。关键操作关键操作通常是位于算法最内层循环的程序步（或语句），通常是位于算法最内层循环的程序步（或语句），是算法中执行次数最多的操作（程序步）是算法中执行次数最多的操作（程序步）。可以通过考察一个程序中关键操作（key operation）的执行次数，来估算算法的渐近时间复杂度。关键操作关键操作通常是位于算法最内层循环的程序步

8、（或语句），是算法中执行次数最通常是位于算法最内层循环的程序步（或语句），是算法中执行次数最多的操作（程序步）多的操作（程序步）。例如：程序2-3 矩阵乘法for(i=0;in;i+)/n+1 for(j=0;jn;j+)/n(n+1)cij=0;/n2for(k=0;kn)Swap(m,n);while(m0)int c=n%m;n=m;m=c;return n;有时候算法时间的计算并非直截了有时候算法时间的计算并非直截了当，当，while循环每次迭代后余数值并循环每次迭代后余数值并非按常数因子递减。如何计算迭代非按常数因子递减。如何计算迭代次数？次数？定理定理2-2 如果如果nm，则，则n

9、 mod m 0，则f(n)=(nm)。渐进紧界（同价函数集合）例子（定理2-4）如果f(n)=amnm+am-1nm-1+a1n+a0是m次多项式，且am0，则f(n)=(nm)。非紧上界记号o非紧下界记号渐近分析中函数比较f(n)=O(g(n)f(n)g(n);f(n)=(g(n)f(n)g(n);f(n)=(g(n)f(n)=g(n);f(n)=o(g(n)f(n)g(n).渐近符号的性质证明：对于任意f1(n)O(f(n)，存在正常数c1和自然数n1，使得对所有n n1，有f1(n)c1f(n)。类似地，对于任意g1(n)O(g(n)，存在正常数c2和自然数n2，使得对所有n n2，有

10、g1(n)c2g(n)。令c3=maxc1,c2，n3=maxn1,n2，则对所有的 n n3，有f1(n)+g1(n)c1f(n)+c2g(n)c3f(n)+c3g(n)=c3(f(n)+g(n)2c3 maxf(n),g(n)=O(maxf(n),g(n)思考题：证明O(f(n)+O(g(n)=O(maxf(n),g(n)顺序搜索算法templateint seqSearch(Type*a,int n,Type k)for(int i=0;in;i+)if(ai=k)return i;return-1;时间复杂度综合分析（例1）（1）最坏情况下：Tmax(n)=max T(I)|size(

11、I)=n=O(n)（2）最好情况下：Tmin(n)=min T(I)|size(I)=n=O(1)（3）平均情况下，假设：搜索成功的概率为p(0p1)；在数组的每个位置i(0in)搜索成功的概率相同，均为 p/n。非递归算法的时间复杂度分析法则：（1）for/while 循环循环体内计算时间*循环次数；（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。templatevoid insertion_sort(Type*a,int n)Type key;/cost times for(int i=

12、1;i=0&ajkey)/c4sum of ti aj+1=aj;/c5 sum of(ti-1)j-;/c6 sum of(ti-1)aj+1=key;/c7 n-1 时间复杂度综合分析（例2）在最好情况下，ti=1,for 1 i n;在最坏情况下，ti i+1,for 1 i n;对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort 达到其最坏情形。while首句：while循环体：算法按时间复杂度分类多项式时间算法渐近时间复杂度有多项式时间限界的算法O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数时间算法渐近时间复杂度为指数函数限界的算法O(2n)O(n!)+=15)2(217)(2nnnTnnT222112222225)2(52)2(52)1(25)2(5)4(5)8(2(2(25)2(5)4(2(25)2(2)(nnnTnnnnTnnnTnnTnTkkk+=+=+=+=-L)(2nO=。主方法（Master方法）主方法的使用