数据结构与算法设计PPT (4).pdf

《数据结构与算法设计PPT (4).pdf》由会员分享，可在线阅读，更多相关《数据结构与算法设计PPT (4).pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 绪论1.5 算法效率分析算法的事前估计：算法的事前估计：算法分析感兴趣的不是具体算法分析感兴趣的不是具体的资源占用量，而是与具体的平台无关、具体的资源占用量，而是与具体的平台无关、具体的输入实例无关，且随着规模增长的值是可预的输入实例无关，且随着规模增长的值是可预测的时间效率变化趋势。测的时间效率变化趋势。算法效率分析：算法效率分析：渐进时间复杂度渐进时间复杂度渐进空间复杂度渐进空间复杂度算法的性能分析算法的性能分析算法的执行时间分析算法的执行时间分析算法的执行时间分析算法的执行时间分析T(n)T(n)的计算的计算 程程 序序 语语 句句 一次执行一次执行 所需程序步数所需程序步数 执

2、行频度执行频度 0 0 1 1 floatfloat s=s=0.0;0.0;1 1 1 1 for(for(intint i=i=0;0;inin;i+i+)1 1 n n+1+1 s+=as+=a i i;1 1 n n returnreturn s s;1 1 1 1 0 0 1 1 总程序步数总程序步数。2 2n+3n+3 语句执行的频度语句执行的频度 2n+32n+3时间复杂度的渐进表示法程序的精确步数没有实际意义，程序步数的数量级别可以程序的精确步数没有实际意义，程序步数的数量级别可以反映程序的实质。反映程序的实质。n n：一个特定算法的“运行工作量”的大小，只依赖于问题：一个特定

3、算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量的规模（通常用整数量n n表示）表示）f(n):f(n):算法中基本操作的执行次数，即它是问题规模的函数。算法中基本操作的执行次数，即它是问题规模的函数。算法的渐进时间复杂度，简称算法时间复杂度记作：算法的渐进时间复杂度，简称算法时间复杂度记作：T(n)=O(f(n)T(n)=O(f(n)表示随问题规模表示随问题规模n n的增大，算法执行时间的增长率与的增大，算法执行时间的增长率与f(n)f(n)的的增长率相同。表示算法执行时间的增长的数量级。增长率相同。表示算法执行时间的增长的数量级。时间复杂度的渐进表示法大大O O表示法定义表示法

4、定义当当NN0NN0时存在一个正的常数时存在一个正的常数c c和和N0N0使得使得T(n)T(n)cFcF(n),(n),则（则（BigBig-OhOh）T(N)T(N)就是就是O(F(n)O(F(n)含义：当含义：当n n增大时，算法的运行时间的增长率小于增大时，算法的运行时间的增长率小于等于等于(n)(n)的增长率。的增长率。算法的渐进分析就是要估计，当数据规模逐步增大算法的渐进分析就是要估计，当数据规模逐步增大时资源开销时资源开销f(n)f(n)的增长趋势，得到一个精确的界限的增长趋势，得到一个精确的界限比较费时费力，也没有必要比较费时费力，也没有必要时间复杂度的渐进表示法从数量级大小比

5、较来考虑，当从数量级大小比较来考虑，当n n增到到一定值后，增到到一定值后，对资源开销影响最大的就是对资源开销影响最大的就是n n的幂次最高的项，所的幂次最高的项，所以使用以使用BigBig-OhOh表示法时不必考虑表示法时不必考虑常数、系数、次要常数、系数、次要项和关系符号项和关系符号。O(nO(n2 2)O(2nO(2n2 2+2n+1)+2n+1)常见的算法时间复杂度：常见的算法时间复杂度：1 1 log log2 2n n n n n nloglog2 2n n n n2 2 n n3 3 2 2n n 3 3n n n n!算法时间复杂度的分析规则算法时间复杂度的分析规则按照程序的结

6、构分析时间复杂度按照程序的结构分析时间复杂度加法规则加法规则针对并列程序段：顺序结构，针对并列程序段：顺序结构，if if结构，结构，switchswitch结构结构T(T(n n,mm)=T1()=T1(n n)+T2()+T2(mm)=O(max(=O(max(f f(n n),),g g(mm)乘法规则乘法规则针对嵌套程序段；针对嵌套程序段；forfor，whilewhile，dowhiledowhileT(T(n n,mm)=T1()=T1(n n)*T2()*T2(mm)=O(=O(f f(n n)*)*g g(mm)时间复杂度的渐进表示法分析规则时间复杂度分析例子例1：x+;s=0

7、;用频度法分析：将x+看成是基本操作，语句频度为T(n)=2算法的时间复杂度：O(1)-常量阶例2:for(i=0;in;i+)/执行n+1次x+;/语句频度为：ns+=x;/语句频度为：nT(n)=2n+n+1=3n+1，则时间复杂度为：O(n)也可以这样考虑：将x自增看成是基本操作，则语句频度为：n其时间复杂度为：O(n)，即时间复杂度为线性阶。例例3:3:矩阵相乘矩阵相乘C=C=AxBAxBfor(for(i i=0;=0;i i n;n;i i+)+)/n+1/n+1for(j=0;j n;for(j=0;j n;j+j+)/n*(n+1)/n*(n+1)c ci ij=0;j=0;/

8、n n2 2for(k=0;k n;k+)/nfor(k=0;k n;k+)/n2 2*(n+1)*(n+1)c ci ij+=aj+=ai ik*bkj;/nk*bkj;/n3 3 T(n)=T(n)=2n2n3 3+3n+3n2 2+2n+1+2n+1算法的时间复杂度：算法的时间复杂度：O(nO(n3 3)计算方法计算方法1 1：由于是一个三重循环，每个循环从：由于是一个三重循环，每个循环从1 1到到n n，则总次数为，则总次数为:n n n n n n=n=n3 3故时故时间复杂度为间复杂度为T(n)=O(nT(n)=O(n3 3)。计算方法计算方法2 2：由于“乘法”运算是本例的基本操

9、作，故整个算法的执行时间与该基本：由于“乘法”运算是本例的基本操作，故整个算法的执行时间与该基本操作（乘法）重复执行的次数操作（乘法）重复执行的次数n n3 3成正比，故时间复杂度为成正比，故时间复杂度为T(n)=O(nT(n)=O(n3 3)。时间复杂度分析例子1-12例例4:4:分析以下程序段的时间复杂度分析以下程序段的时间复杂度i i=1;=1;/语句频度为：语句频度为：while(while(i i=n)=n)i i=i i*2*2/语句频度为：语句频度为：f(n)f(n)因为：因为：f(n)f(n)nn，即：，即：f(n)logf(n)log2 2n n，取最大值，取最大值f(n)=

10、logf(n)=log2 2n n，则该程序的时间复杂度为：则该程序的时间复杂度为：T(n)=1+T(n)=1+f(n)f(n)=1+log=1+log2 2n=O(logn=O(log2 2n)n)时间复杂度计算1-13时间复杂度计算算法中基本操作重复执行的次数随问题的输入数算法中基本操作重复执行的次数随问题的输入数据集不同而不同据集不同而不同例例6 6：在数组：在数组AnAn查找给定值查找给定值K K(1)(1)i i=0;=0;(2)while(2)while(i i=n=n-1 1&A&Ai i!=K)!=K)(3)(3)i i=i+1;=i+1;(4)return(4)return

11、i i;最好情况的时间复杂度最好情况的时间复杂度 T(n)=O(1)A0T(n)=O(1)A0等于等于K K最坏情况的时间复杂度最坏情况的时间复杂度 T(n)=O(n)AnT(n)=O(n)An-11等于等于平均时间复杂度平均时间复杂度：所有可能的输入实例以等概率出现的情况所有可能的输入实例以等概率出现的情况T(n)=(1+2+.+n)/nT(n)=(1+2+.+n)/n算法的时间复杂度：算法的时间复杂度：O(n)O(n)1-14时间复杂度按数量递增排列及增长率一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执行的次数是固定的。的算法，它的基本运算执行的次数是固定的。因此，总的

12、时间由一个常数（即零次多项式）来限界。而一个时因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为间为O(nO(n2 2)的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(logO(1)O(log2 2n)O(n)O(nlogn)O(n)O(nlog2 2n)O(nn)O(n2 2)O(n)O(n3 3)指数时间的关系为：指数时间的关系为：O(O(n nk k)O(2)O(2n n)O(n!)O()O(n!)O(n nn n)当当n n取得很大时，指数时间算法和

13、多项式时间算法在所需时间上非取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。法化简为多项式时间算法，那就取得了一个伟大的成就。增长率函数曲线增长率函数曲线存储空间的固定部分存储空间的固定部分程序指令代码的空间，常数、简单变量、定长成分程序指令代码的空间，常数、简单变量、定长成分(如数如数组元素、结构成分、对象的数据成员等组元素、结构成分、对象的数据成员等)变量所占的空间变量所占的空间可变部分可变部分尺寸与实例特性有关的成分变量所

14、占空间、引用变量所尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过占空间、递归栈所用的空间、通过newnew和和deletedelete命令动态命令动态使用的空间使用的空间空间复杂度的度量空间复杂度的度量只考虑程序使用的可变部分空间使用情况只考虑程序使用的可变部分空间使用情况空间复杂度度量一个算法为解决问题所用辅助存储空间的大小，一个算法为解决问题所用辅助存储空间的大小，只依赖于问题的规模（通常用整数量只依赖于问题的规模（通常用整数量n n表示），表示），即它是问题规模的函数。即它是问题规模的函数。算法的渐进空间复杂度，简称算法空间复杂度记算法的渐进空间复杂度，简

15、称算法空间复杂度记作：作：S S(n)=O(f(n)(n)=O(f(n)表示最表示最坏情况坏情况下，算法所下，算法所需需辅助存储空间的数量辅助存储空间的数量是实例是实例特性特性n n的的某某个函数的数量级，表示所个函数的数量级，表示所需需存存储空间增长的数量级。储空间增长的数量级。渐进空间复杂度分析例例解法解法1 1 先先计算计算x x 的幂的幂,存于存于p powerower 中中,再再分分别别乘以乘以相应相应的系数的系数#define N 100 define N 100float efloat ev val alu uate(float ate(float coefcoef ,float

16、 x,int n),float x,int n)float float p powerower N N,f;int,f;int i i;for(for(p powerower 0 0=1,=1,i i=1;=1;i i=n;=n;i i+)+)p powerower i i=x*=x*p powerower i i-1 1;for(f=0,for(f=0,i i=0;=0;i i=N;=0;=0;i i-)f=f*f=f*x+coefx+coef i i;retretu urn(f);rn(f);时间复杂度为时间复杂度为O(n)O(n).空间复杂度为空间复杂度为O(1)O(1)xxxxaaaa

17、axfnn).)(.()(1210+=-小结n算法的效率可以从运行时间和运行时所用的空间算法的效率可以从运行时间和运行时所用的空间开销进行开销进行评价评价；n绝绝对的时间和空间开销即对的时间和空间开销即难难以以获获取，不取，不能准能准确确反反映映程序的实程序的实质质，所以一，所以一般般对效率的度量对效率的度量采采用事前用事前分析的分析的方方法，即法，即根根据算法据算法处理处理的步的步骤骤，得到算法，得到算法的渐进时间复杂度和算法的渐进空间复杂度的渐进时间复杂度和算法的渐进空间复杂度描述描述，从而确定算法的时空从而确定算法的时空需求需求随问题规模的变化趋势，随问题规模的变化趋势，从而可以确定算法的数量级。从而可以确定算法的数量级。