1、数据结构与算法基础数据结构与算法基础 第三部分第三部分：算法及效率度量：算法及效率度量n算法、算法的特性算法、算法的特性n算法好坏的评价标准算法好坏的评价标准n算法的性能度量方法算法的性能度量方法n渐进时间复杂度渐进时间复杂度n渐进空间复杂度渐进空间复杂度主要内容算法算法算法的特性算法的特性算法的分类算法的分类 void selectSort(int a,const int n)/对对n个整数个整数a0,a1,an-1,按非递减顺序排序按非递减顺序排序 for(int i=0;i n-1;i+)int k=i;/从从ai检查到检查到an-1,找最小的整数找最小的整数,在在ak for(int
2、j=i+1;j n;j+)if(aj ak)k=j;/k指示当前找到的最小整数指示当前找到的最小整数 int temp=ai;ai=ak;ak=temp;/交换交换ai与与ak 第一个层次第一个层次程序不包含语法错误程序不包含语法错误第二个层次第二个层次输入输入100 输出输出1输入输入0 输出输出0输入输入100 输出输出1第三个层次第三个层次输入输入100 输出输出1输入输入1 输出输出1输入输入0 输出输出0输入输入-1 输出输出-1输入输入-100 输出输出-1第四个层次第四个层次所有可能的输入所有可能的输入算法效率的度量算法效率的度量n实验的方法实验的方法：采用实际数据测试程序的执行
3、时间；：采用实际数据测试程序的执行时间；n仿真的方法仿真的方法：模拟数据进行测试；：模拟数据进行测试；n在算法中的某些部位插装时间函数在算法中的某些部位插装时间函数 time()或者或者clock()测定算法完成某一功能所花费的时间。测定算法完成某一功能所花费的时间。n采用开发工具提供的时间测量工具采用开发工具提供的时间测量工具profile算法的后期测试算法的后期测试 void TimeSearch()/在在0.1000中搜索中搜索0,10,90,100,200,1000 int a1001,n20;for(int j=0;j=1000;j+)aj=j;/a1=1,a2=2,for(j=0;
4、j 10;j+)nj=10*j;/n0=0,n1=10,n2=20 nj+10=100*(j+1);/n10=100,n11=200,n12=300.printf(%12s%12s%12sn,n,500000,1);希望软件执行时间可预测希望软件执行时间可预测 算法分析算法分析感兴趣的不是具体的资源占用量，而是与具体感兴趣的不是具体的资源占用量，而是与具体的平台无关、具体的输入实例无关，且随着规模增长的的平台无关、具体的输入实例无关，且随着规模增长的值是可预测的。值是可预测的。希望了解软件执行时间的变化趋势希望了解软件执行时间的变化趋势 与问题与问题规模之间的关系，用一定的规模数据作为输入时规
5、模之间的关系，用一定的规模数据作为输入时程序所需的基本操作的次数来描述时间效率程序所需的基本操作的次数来描述时间效率 忽略细节忽略细节 完成完成一个基本操作所需要的时间应该与具体的被操作数一个基本操作所需要的时间应该与具体的被操作数无关无关 算法的复杂性分析算法的复杂性分析 float sum(float a,const int n)1 2 float s=0.0;3 for(int i=0;i n;i+)4 s+=ai;5 return s;6 程序的精确步数没有实际意义，程序步数的数量级别可以程序的精确步数没有实际意义，程序步数的数量级别可以反映程序的实质。反映程序的实质。n：一个特定算法
6、的一个特定算法的“运行工作量运行工作量”的大小，只依赖于问题的大小，只依赖于问题的规模（通常用整数量的规模（通常用整数量n表示）表示）f(n):算法中基本操作的执行次数，即它是问题规模的函数。算法中基本操作的执行次数，即它是问题规模的函数。算法的渐进时间复杂度，简称算法时间复杂度记作算法的渐进时间复杂度，简称算法时间复杂度记作：T(n)=O(f(n)表示随问题规模表示随问题规模n的增大，算法执行时间的增长率与的增大，算法执行时间的增长率与f(n)的的增长率相同。表示算法执行时间的增长的数量级。增长率相同。表示算法执行时间的增长的数量级。n大大O表示法定义表示法定义 当当NN0时存在一个正的常数
7、时存在一个正的常数c和和N0，使得，使得T(n)cF(n),则（则（Big-Oh）T(N)就是就是O(F(n)含义：当含义：当n增大时，算法的运行时间的增长率小于等于增大时，算法的运行时间的增长率小于等于(n)的增长率的增长率。算法的渐进分析就是要估计，当数据规模逐步增大时资算法的渐进分析就是要估计，当数据规模逐步增大时资源开销源开销f(n)的增长趋势，得到一个精确的界限比较费时的增长趋势，得到一个精确的界限比较费时费力，也没有必要费力，也没有必要 时间复杂度的渐进表示法 1 log2n n nlog2n n2 n3 2n 3n n!加法规则加法规则 针对并列程序段：顺序结构，针对并列程序段：
8、顺序结构，if结构，结构，switch结构结构 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)乘法规则乘法规则 针对嵌套程序段；针对嵌套程序段；for，while，dowhile T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)时间复杂度计算例例3:3:矩阵相乘矩阵相乘C=C=AxBAxB for(i=0;i n;i+)/n+1 for(j=0;j n;j+)/n*(n+1)cij=0;/n2 for(k=0;k n;k+)/n2*(n+1)cij+=aik*bkj;/n3 T(n)=2n3+3n2+2n+1算法的时间复杂度：算法的时间复杂度：O(nO(n3
9、3)计算方法计算方法1 1：由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1 1到到n n，则总次数为，则总次数为:n nn nn n=n=n3 3 故时间复杂度为故时间复杂度为T(nT(n)=O(n)=O(n3 3)。计算方法计算方法2 2：由于：由于“乘法乘法”运算是本例的基本操作，故整个算法的执行时间运算是本例的基本操作，故整个算法的执行时间与该基本操作（乘法）重复执行的次数与该基本操作（乘法）重复执行的次数n n3 3成正比，故时间复杂度为成正比，故时间复杂度为T(nT(n)=O(n)=O(n3 3)。时间复杂度计算1-26 例例4:4:分析以下程序段的时间复杂度分析以下
10、程序段的时间复杂度i=1;i=1;/语句频度为：语句频度为：while(i=n)while(i=n)i=i i=i*2 2 /语句频度为：语句频度为：f(nf(n)因为：因为：f(n)f(n)nn，即：，即：f(n)logf(n)log2 2n n，取最大值，取最大值 f(nf(n)=log)=log2 2n n，则该程序的时间复杂度为：则该程序的时间复杂度为：T(nT(n)=1+)=1+f(n)f(n)=1+log=1+log2 2n=O(logn=O(log2 2n)n)时间复杂度计算1-27 时间复杂度计算 算法中基本操作重复执行的次数随问题的输入数据集不算法中基本操作重复执行的次数随问
11、题的输入数据集不同而不同同而不同例例6 6：在数组：在数组AnAn 查找给定值查找给定值K K(1)i=0;(1)i=0;(2)while(i=n-1(2)while(i=n-1&AiAi!=K)!=K)(3)i=i+1;(3)i=i+1;(4)return i;(4)return i;最好情况的时间复杂度最好情况的时间复杂度 T(nT(n)=O(1)A0)=O(1)A0等于等于K K最坏情况的时间复杂度最坏情况的时间复杂度 T(nT(n)=)=O(nO(n)An-1)An-1等于等于平均时间复杂度平均时间复杂度：所有可能的输入实例以等概率出现的情况所有可能的输入实例以等概率出现的情况 T(n
12、T(n)=(1+2+.+)=(1+2+.+n)/nn)/n算法的时间复杂度：算法的时间复杂度：O(nO(n)1-28 时间复杂度按数量递增排列及增长率 一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执行的次数是固定的。的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为为O(nO(n2 2)的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(log
13、O(1)O(log2 2n)n)O(nO(n)O(nlog)O(nlog2 2n)O(nn)O(n2 2)O(n)O(n3 3)指数时间的关系为：指数时间的关系为：O(nO(nk k)O(2)O(2n n)O(nO(n!)!)O(nO(nn n)当当n n取得很大时，指数时间算法和多项式时间算法在所需时间上非取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。化简为多项式时间算法，那就取得了一个伟大的成就。增长率函数曲线增长率函数
14、曲线例例nnxaxaxaaxf.)(2210问题规模为问题规模为n n 算法时间复杂度算法时间复杂度:O(nO(n)空间复杂度：空间复杂度：O(nO(n)xxxxaaaaaxfnn).)(.()(1210n算法是对于问题解决步骤的描述，是一个指令的系列；算法是对于问题解决步骤的描述，是一个指令的系列；n算法具有确定性、有穷性、有效性；算法具有确定性、有穷性、有效性；n算法的评价可以从正确、可读、健壮和效率四个方面进行算法的评价可以从正确、可读、健壮和效率四个方面进行评价好坏；评价好坏；n算法的效率可以从运行时间和运行时所用的空间开销进行算法的效率可以从运行时间和运行时所用的空间开销进行评价；评价；n绝对的时间和空间开销即难以获取，有不能准确反映程序绝对的时间和空间开销即难以获取，有不能准确反映程序的实质，所以一般对效率的度量采用事前分析的方法，即的实质，所以一般对效率的度量采用事前分析的方法，即根据算法处理的步骤，得到算法的渐进时间复杂度和算法根据算法处理的步骤，得到算法的渐进时间复杂度和算法的渐进空间复杂度描述，从而确定算法的时空需求随问题的渐进空间复杂度描述，从而确定算法的时空需求随问题规模的变化趋势，从而可以确定算法的数量级。规模的变化趋势，从而可以确定算法的数量级。
