数据结构概述优秀PPT.ppt

《数据结构概述优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构概述优秀PPT.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构与算法基础数据结构与算法基础 第三部分：算法及效率度量第三部分：算法及效率度量n算法、算法的特性算法、算法的特性n算法好坏的评价标准算法好坏的评价标准n算法的性能度量方法算法的性能度量方法n渐进时间困难度渐进时间困难度n渐进空间困难度渐进空间困难度主要内容算法：对特定问题的求解过程的描述，是指令的算法：对特定问题的求解过程的描述，是指令的算法：对特定问题的求解过程的描述，是指令的算法：对特定问题的求解过程的描述，是指令的有限序列，也就是为解决某一具体问题而实行的有限序列，也就是为解决某一具体问题而实行的有限序列，也就是为解决某一具体问题而实行的有限序列，也就是为解决某一具体问题而实行的

2、具有有限的操作步骤。具有有限的操作步骤。具有有限的操作步骤。具有有限的操作步骤。程序是算法的实现，计算机依据程序逐步执行算程序是算法的实现，计算机依据程序逐步执行算程序是算法的实现，计算机依据程序逐步执行算程序是算法的实现，计算机依据程序逐步执行算法，实现对问题的求解。法，实现对问题的求解。法，实现对问题的求解。法，实现对问题的求解。定义：定义：定义：定义：一个有穷的指令集，这些指令为解决某一特定一个有穷的指令集，这些指令为解决某一特定一个有穷的指令集，这些指令为解决某一特定一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。任务规定了一个运算序列。任务规定了一个运算序列。任务规定

3、了一个运算序列。算法算法五个特性：五个特性：五个特性：五个特性：输入输入输入输入 有有有有0 0个或多个输入个或多个输入个或多个输入个或多个输入输出输出输出输出 有一个或多个输出（处理结果）有一个或多个输出（处理结果）有一个或多个输出（处理结果）有一个或多个输出（处理结果）确定性确定性确定性确定性 每步定义都是准确、无歧义的每步定义都是准确、无歧义的每步定义都是准确、无歧义的每步定义都是准确、无歧义的有穷性有穷性有穷性有穷性 算法应在执行有穷步后结束算法应在执行有穷步后结束算法应在执行有穷步后结束算法应在执行有穷步后结束有效性有效性有效性有效性 每一条运算应足够基本能被执行每一条运算应足够基本

4、能被执行每一条运算应足够基本能被执行每一条运算应足够基本能被执行算法的特性算法的特性常用的设计方法：常用的设计方法：常用的设计方法：常用的设计方法：穷举法穷举法穷举法穷举法贪心法贪心法贪心法贪心法分治法分治法分治法分治法回溯法回溯法回溯法回溯法动态规划法动态规划法动态规划法动态规划法裁剪与分枝界限法裁剪与分枝界限法裁剪与分枝界限法裁剪与分枝界限法并行算法并行算法并行算法并行算法算法的分类算法的分类 事例学习：事例学习：事例学习：事例学习：选择排序问题选择排序问题选择排序问题选择排序问题 明确问题：明确问题：明确问题：明确问题：非递减排序非递减排序非递减排序非递减排序 解决方案：解决方案：解决方

5、案：解决方案：逐个选择最小数据逐个选择最小数据逐个选择最小数据逐个选择最小数据 算法框架：算法框架：算法框架：算法框架：for(intfor(int i=i=0;0;i n-i n-1;1;i+i+)/)/n n-1-1趟趟趟趟 从从从从a a i i 检查到检查到检查到检查到a a n-n-1;1;若最小的整数在若最小的整数在若最小的整数在若最小的整数在a a k k,交换交换交换交换a a i i 与与与与a a k k;细化程序：细化程序：细化程序：细化程序：程序程序程序程序 SelectSortSelectSort 算法设计过程算法设计过程 自顶向下，逐步求精自顶向下，逐步求精 voi

6、d 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 j=i+1;j n;j+)if(aj 0)if(x 0)y=1;y=1;else if else if(x=0)(x=0)y=0;y=0;else else y=-1;y=-1;return y;return y;第一个层次第一个层次程序不包含语法错误程序不包含语法错误int sign(int x)int sign(i

7、nt x)int y;int y;if(if(x 1x 1)y=1;y=1;else if(x=0)else if(x=0)y=0;y=0;else else y=-1;y=-1;return y;return y;其次个层次其次个层次输入输入100 输出输出1输入输入0 输出输出0输入输入100 输出输出1int sign(int x)int sign(int x)int y;int y;if(x=1)if(x=1)y=1;y=1;else if(x=0)else if(x=0)y=0;y=0;else else y=-1;y=-1;return y;return y;第三个层次第三个层次输

8、入输入100 输出输出1输入输入1 输出输出1输入输入0 输出输出0输入输入-1 输出输出-1输入输入-100 输出输出-1int sign(int x)int sign(int x)int y;int y;if(x 0)if(x 0)y=1;y=1;else if(x=0)else if(x=0)y=0;y=0;else else y=-1;y=-1;if(x=0 x1234)if(x=0 x1234)y=0;y=0;return y;return y;第四个层次第四个层次全部可能的输入全部可能的输入 解决同一个问题存在多种算法，如何评估各种算法的解决同一个问题存在多种算法，如何评估各种算法

9、的解决同一个问题存在多种算法，如何评估各种算法的解决同一个问题存在多种算法，如何评估各种算法的好坏？好坏？好坏？好坏？运行算法所须要的计算机资源运行算法所须要的计算机资源运行算法所须要的计算机资源运行算法所须要的计算机资源时间和空间时间和空间时间和空间时间和空间 评价一个算法的优劣的重要依据看执行该算法的程序评价一个算法的优劣的重要依据看执行该算法的程序评价一个算法的优劣的重要依据看执行该算法的程序评价一个算法的优劣的重要依据看执行该算法的程序占用多少计算机资源占用多少计算机资源占用多少计算机资源占用多少计算机资源 程序所用算法运行时所要花费的时间代价程序所用算法运行时所要花费的时间代价程序所

10、用算法运行时所要花费的时间代价程序所用算法运行时所要花费的时间代价 程序中运用的数据结构占用的空间代价程序中运用的数据结构占用的空间代价程序中运用的数据结构占用的空间代价程序中运用的数据结构占用的空间代价 如何评价？如何评价？如何评价？如何评价？算法的后期测试：试验方法、仿真方法算法的后期测试：试验方法、仿真方法算法的后期测试：试验方法、仿真方法算法的后期测试：试验方法、仿真方法 算法的事前估计：分析的方法算法的事前估计：分析的方法算法的事前估计：分析的方法算法的事前估计：分析的方法算法效率的度量算法效率的度量n试验的方法：接受实际数据测试程序的执行时间；试验的方法：接受实际数据测试程序的执行

11、时间；n仿真的方法：模拟数据进行测试；仿真的方法：模拟数据进行测试；n在算法中的某些部位插装时间函数在算法中的某些部位插装时间函数n time()或者或者clock()n 测定算法完成某一功能所花费的时间。测定算法完成某一功能所花费的时间。n接受开发工具供应的时间测量工具接受开发工具供应的时间测量工具profile算法的后期测试算法的后期测试依次搜寻依次搜寻依次搜寻依次搜寻(Sequenial Search)(Sequenial Search)行行行行 int seqsearch(int a,const int n,int seqsearch(int a,const int n,const i

12、nt x)/a0,an-1 const int x)/a0,an-1 1 1 2 int i=0;2 int i=0;3 while(i n&ai!=x)3 while(i n&ai!=x)4 i+;4 i+;5 if(i=n)return-1;5 if(i=n)return-1;6 return i;6 return i;7 7 插装 clock()的计时程序 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;j 10;j+)

13、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);forfor (j=j=0 0;j j 2020;j+j+)clock_tclock_t startstart,stop stop;start=clock start=clock()();long long count=500000count=500000;whilewhile(count-)(count-)intint k=seqsearchk=seqsearch(a,a,1001,1001,n

14、 n j j);stop=stop=clockclock()();double double runTimerunTime=stop =stop startstart;printfprintf(“%12d%12d%12.6fn”,nj,runTime,(“%12d%12d%12.6fn”,nj,runTime,double(runTime)/500000);double(runTime)/500000);程序测试结果输出程序在计算机上运行所需时间的影响因素程序在计算机上运行所需时间的影响因素程序在计算机上运行所需时间的影响因素程序在计算机上运行所需时间的影响因素算法本身选用的策略算法本身选用的

15、策略算法本身选用的策略算法本身选用的策略问题的规模问题的规模问题的规模问题的规模规模越大，消耗时间越多规模越大，消耗时间越多规模越大，消耗时间越多规模越大，消耗时间越多书写程序的语言书写程序的语言书写程序的语言书写程序的语言语言越高级，消耗时间越多语言越高级，消耗时间越多语言越高级，消耗时间越多语言越高级，消耗时间越多编译产生的机器代码质量编译产生的机器代码质量编译产生的机器代码质量编译产生的机器代码质量机器执行指令的速度机器执行指令的速度机器执行指令的速度机器执行指令的速度为便于比较算法本身的优劣为便于比较算法本身的优劣为便于比较算法本身的优劣为便于比较算法本身的优劣应解除其它影响算法效率的

16、因素应解除其它影响算法效率的因素应解除其它影响算法效率的因素应解除其它影响算法效率的因素希望软件执行时间可预料希望软件执行时间可预料 算法分析感爱好的不是具体的资源占用量，而是与具算法分析感爱好的不是具体的资源占用量，而是与具体的平台无关、具体的输入实例无关，且随着规模增长体的平台无关、具体的输入实例无关，且随着规模增长的值是可预料的。算法的事前估计的值是可预料的。算法的事前估计希望了解软件执行时间的变更趋势希望了解软件执行时间的变更趋势 与问题规模之间的关系，用确定的规模数据作为输入与问题规模之间的关系，用确定的规模数据作为输入时程序所需的基本操作的次数来描述时间效率时程序所需的基本操作的次

17、数来描述时间效率忽视细微环节忽视细微环节 完成一个基本操作所须要的时间应当与具体的被操作完成一个基本操作所须要的时间应当与具体的被操作数无关数无关 算法的困难性分析算法的困难性分析例例例例 以迭代方式求累加和的函数以迭代方式求累加和的函数以迭代方式求累加和的函数以迭代方式求累加和的函数行行行行 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 程序步确定方法程序步确定方法程序步确定方法程序步确定方法w w 插入计数全局变量插入计数全局变量插入计数全局变量插入计数全局变量

18、countcountw w 建表，列出个语句的程序步建表，列出个语句的程序步建表，列出个语句的程序步建表，列出个语句的程序步计算计算累加和累加和程序程序程序步数程序步数计算工作表格计算工作表格 语句执行的频度语句执行的频度语句执行的频度语句执行的频度 2n+32n+3程序的精确步数没有实际意义，程序步数的数量级别可以程序的精确步数没有实际意义，程序步数的数量级别可以反映程序的实质。反映程序的实质。n：一个特定算法的：一个特定算法的“运行工作量运行工作量”的大小，只依靠于问题的大小，只依靠于问题的规模（通常用整数量的规模（通常用整数量n表示）表示）f(n):算法中基本操作的执行次数，即它是问题规

19、模的函数。算法中基本操作的执行次数，即它是问题规模的函数。算法的渐进时间困难度，简称算法时间困难度记作：算法的渐进时间困难度，简称算法时间困难度记作：T(n)=O(f(n)表示随问题规模表示随问题规模n的增大，算法执行时间的增长率与的增大，算法执行时间的增长率与f(n)的的增长率相同。表示算法执行时间的增长的数量级。增长率相同。表示算法执行时间的增长的数量级。时间困难度的渐进表示法n大大O表示法定义表示法定义n 当当NN0时存在一个正的常数时存在一个正的常数c和和N0，使得，使得T(n)cF(n),则（则（Big-Oh）T(N)就是就是O(F(n)n 含义：当含义：当n增大时，算法的运行时间的

20、增长率小于等增大时，算法的运行时间的增长率小于等于于(n)的增长率。的增长率。n算法的渐进分析就是要估计，当数据规模逐步增大时算法的渐进分析就是要估计，当数据规模逐步增大时资源开销资源开销f(n)的增长趋势，得到一个精确的界限比较费的增长趋势，得到一个精确的界限比较费时费劲，也没有必要时费劲，也没有必要 时间困难度的渐进表示法n n从数量级大小比较来考虑，当从数量级大小比较来考虑，当从数量级大小比较来考虑，当从数量级大小比较来考虑，当n n增到到确定值后，对资源开增到到确定值后，对资源开增到到确定值后，对资源开增到到确定值后，对资源开销影响最大的就是销影响最大的就是销影响最大的就是销影响最大的

21、就是n n的幂次最高的项，所以运用的幂次最高的项，所以运用的幂次最高的项，所以运用的幂次最高的项，所以运用Big-OhBig-Oh表示表示表示表示法时不必考虑常数、系数、次要项和关系符号。法时不必考虑常数、系数、次要项和关系符号。法时不必考虑常数、系数、次要项和关系符号。法时不必考虑常数、系数、次要项和关系符号。n n O(n2)O(2n2+2n+1)O(n2)O(2n2+2n+1)n n常见的算法时间困难度：常见的算法时间困难度：常见的算法时间困难度：常见的算法时间困难度：n n 1 log2n n nlog2n n2 n3 2n 3n n!1 log2n n nlog2n n2 n3 2n

22、 3n n!n n算法时间困难度的分析规则算法时间困难度的分析规则算法时间困难度的分析规则算法时间困难度的分析规则n n 依据程序的结构分析时间困难度依据程序的结构分析时间困难度依据程序的结构分析时间困难度依据程序的结构分析时间困难度时间困难度的渐进表示法加法规则加法规则 针对并列程序段：依次结构，针对并列程序段：依次结构，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)时间困难度计算例例例例

23、1 1：x+;s=0;x+;s=0;用频度法分析：将用频度法分析：将用频度法分析：将用频度法分析：将x+x+看成是基本操作，语句频度为看成是基本操作，语句频度为看成是基本操作，语句频度为看成是基本操作，语句频度为T(n)=2T(n)=2算法的时间困难度：算法的时间困难度：算法的时间困难度：算法的时间困难度：O(1)-O(1)-常量阶常量阶常量阶常量阶例例例例2:for(i=0;in;i+)2:for(i=0;in;i+)/执行执行执行执行n+1n+1次次次次 x+;/x+;/语句频度为：语句频度为：语句频度为：语句频度为：n n s+=x;/s+=x;/语句频度为：语句频度为：语句频度为：语句

24、频度为：n n T(n)=2n+n+1=3n+1T(n)=2n+n+1=3n+1，则时间困难度为：，则时间困难度为：，则时间困难度为：，则时间困难度为：O(n)O(n)也可以这样考虑：将也可以这样考虑：将也可以这样考虑：将也可以这样考虑：将x x自增看成是基本操作，则语句频度为：自增看成是基本操作，则语句频度为：自增看成是基本操作，则语句频度为：自增看成是基本操作，则语句频度为：n n其其其其时间困难度为：时间困难度为：时间困难度为：时间困难度为：O(n)O(n)，即时间困难度为线性阶。，即时间困难度为线性阶。，即时间困难度为线性阶。，即时间困难度为线性阶。例例3:3:矩阵相乘矩阵相乘C=Ax

25、BC=AxB for(i=0;i n;i+)for(i=0;i n;i+)/n+1/n+1 for(j=0;j n;j+)/n*(n+1)for(j=0;j n;j+)/n*(n+1)cij=0;cij=0;/n2n2 for(k=0;k n;k+)/n2*(n+1)for(k=0;k n;k+)/n2*(n+1)cij+=aik*bkj;/n3 cij+=aik*bkj;/n3 T(n)=2n3+3n2+2n+1 T(n)=2n3+3n2+2n+1算法的时间困难度：算法的时间困难度：O(n3)O(n3)计算方法计算方法1 1：由于是一个三重循环，每个循环从：由于是一个三重循环，每个循环从1

26、1到到n n，则总次数为，则总次数为:nnn=n3 nnn=n3 故时间困难度为故时间困难度为T(n)=O(n3)T(n)=O(n3)。计算方法计算方法2 2：由于：由于“乘法乘法”运算是本例的基本操作，故整个算法的执行运算是本例的基本操作，故整个算法的执行时间与该基本操作（乘法）重复执行的次数时间与该基本操作（乘法）重复执行的次数n3n3成正比，故时间困难成正比，故时间困难度为度为T(n)=O(n3)T(n)=O(n3)。时间困难度计算1-26 例例4:4:分析以下程序段的时间困难度分析以下程序段的时间困难度i=1;i=1;/语句频度为：语句频度为：while(i=n)while(i=n)i

27、=i*2 i=i*2/语句频度为：语句频度为：f(n)f(n)因为：因为：f(n)nf(n)n，即：，即：f(n)log2nf(n)log2n，取最大值，取最大值 f(n)=log2n f(n)=log2n，则该程序的时间困难度为：则该程序的时间困难度为：T(n)=1+f(n)=1+log2n=O(log2n)T(n)=1+f(n)=1+log2n=O(log2n)时间困难度计算1-27 时间困难度计算算法中基本操作重复执行的次数随问题的输入数据集不算法中基本操作重复执行的次数随问题的输入数据集不同而不同同而不同例例6 6：在数组：在数组AnAn查找给定值查找给定值K K(1)i=0;(1)i

28、=0;(2)while(i=n-1&Ai!=K)(2)while(i=n-1&Ai!=K)(3)i=i+1;(3)i=i+1;(4)return i;(4)return i;最好状况的时间困难度最好状况的时间困难度 T(n)=O(1)A0 T(n)=O(1)A0等于等于K K最坏状况的时间困难度最坏状况的时间困难度 T(n)=O(n)An-1 T(n)=O(n)An-1等于等于平均时间困难度：平均时间困难度：全部可能的输入实例以等概率出现的状况全部可能的输入实例以等概率出现的状况 T(n)=(1+2+.+n)/n T(n)=(1+2+.+n)/n算法的时间困难度：算法的时间困难度：O(n)O(

29、n)1-28 时间困难度按数量递增排列及增长率一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执行的次数是固定的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为一个时间为O(n2)O(n2)的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(1)O(log2n)O(n)O(nlog2n)O(n

30、2)O(n3)指数时间的关系为：指数时间的关系为：O(nk)O(2n)O(n!)O(nn)O(nk)O(2n)O(n!)O(nn)当当n n取得很大时，指数时间算法和多项式时间算法在所需时取得很大时，指数时间算法和多项式时间算法在所需时间上特别悬殊。因此，只要有人能将现有指数时间算法中的任间上特别悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个宏大的成何一个算法化简为多项式时间算法，那就取得了一个宏大的成就。就。增长率函数曲线增长率函数曲线 存储空间的固定部分存储空间的固定部分存储空间的固定部分存储空间的固定部分程序指令代码的空间，常数、简洁变量、定

31、长成分程序指令代码的空间，常数、简洁变量、定长成分程序指令代码的空间，常数、简洁变量、定长成分程序指令代码的空间，常数、简洁变量、定长成分(如数如数如数如数组元素、结构成分、对象的数据成员等组元素、结构成分、对象的数据成员等组元素、结构成分、对象的数据成员等组元素、结构成分、对象的数据成员等)变量所占的空间变量所占的空间变量所占的空间变量所占的空间 可变部分可变部分可变部分可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所尺寸与实例特性有关的成分变量所占空间、引用变量所尺寸与实例特性有关的成分变量所占空间、引用变量所尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间

32、、通过占空间、递归栈所用的空间、通过占空间、递归栈所用的空间、通过占空间、递归栈所用的空间、通过newnew和和和和deletedelete吩咐动态吩咐动态吩咐动态吩咐动态运用的空间运用的空间运用的空间运用的空间 空间困难度的度量空间困难度的度量空间困难度的度量空间困难度的度量 只考虑程序运用的可变部分空间运用状况只考虑程序运用的可变部分空间运用状况只考虑程序运用的可变部分空间运用状况只考虑程序运用的可变部分空间运用状况空间困难度度量渐进的空间困难度渐进的空间困难度渐进的空间困难度渐进的空间困难度一个算法为解决问题所用协助存储空间的大小，一个算法为解决问题所用协助存储空间的大小，一个算法为解决

33、问题所用协助存储空间的大小，一个算法为解决问题所用协助存储空间的大小，只依靠于问题的规模（通常用整数量只依靠于问题的规模（通常用整数量只依靠于问题的规模（通常用整数量只依靠于问题的规模（通常用整数量n n表示），表示），表示），表示），即它是问题规模的函数。即它是问题规模的函数。即它是问题规模的函数。即它是问题规模的函数。算法的渐进空间困难度，简称算法空间困难度记算法的渐进空间困难度，简称算法空间困难度记算法的渐进空间困难度，简称算法空间困难度记算法的渐进空间困难度，简称算法空间困难度记作：作：作：作：S(n)=O(f(n)S(n)=O(f(n)表示最坏状况下，算法所需协助存储空间的数量表示最

34、坏状况下，算法所需协助存储空间的数量表示最坏状况下，算法所需协助存储空间的数量表示最坏状况下，算法所需协助存储空间的数量是实例特性是实例特性是实例特性是实例特性n n的某个函数的数量级，表示所需存的某个函数的数量级，表示所需存的某个函数的数量级，表示所需存的某个函数的数量级，表示所需存储空间增长的数量级。储空间增长的数量级。储空间增长的数量级。储空间增长的数量级。例例解法解法解法解法1 1 1 1 先计算先计算先计算先计算x x x x 的幂的幂的幂的幂,存于存于存于存于power power power power 中中中中,再分别乘以相应的系数再分别乘以相应的系数再分别乘以相应的系数再分别

35、乘以相应的系数#define N 100#define N 100float evaluate(float coef,float x,int n)float evaluate(float coef,float x,int n)float powerN,f;int i;float powerN,f;int i;for(power 0=1,i=1;i=n;i+)for(power 0=1,i=1;i=n;i+)poweri=x*poweri-1;poweri=x*poweri-1;for(f=0,i=0;i=N;i+)for(f=0,i=0;i=0;i-)for(f=coefn,i=n-1;i=0

36、;i-)f=f*x+coefi;f=f*x+coefi;return(f);return(f);时间困难度为时间困难度为时间困难度为时间困难度为O(n).O(n).空间困难度为空间困难度为空间困难度为空间困难度为O(1)O(1)n算法是对于问题解决步骤的描述，是一个指令的系列；算法是对于问题解决步骤的描述，是一个指令的系列；n算法具有确定性、有穷性、有效性；算法具有确定性、有穷性、有效性；n算法的评价可以从正确、可读、健壮和效率四个方面进行算法的评价可以从正确、可读、健壮和效率四个方面进行评价好坏；评价好坏；n算法的效率可以从运行时间和运行时所用的空间开销进行算法的效率可以从运行时间和运行时所用的空间开销进行评价；评价；n确定的时间和空间开销即难以获得，有不能精确反映程序确定的时间和空间开销即难以获得，有不能精确反映程序的实质，所以一般对效率的度量接受事前分析的方法，即的实质，所以一般对效率的度量接受事前分析的方法，即依据算法处理的步骤，得到算法的渐进时间困难度和算法依据算法处理的步骤，得到算法的渐进时间困难度和算法的渐进空间困难度描述，从而确定算法的时空需求随问题的渐进空间困难度描述，从而确定算法的时空需求随问题规模的变更趋势，从而可以确定算法的数量级。规模的变更趋势，从而可以确定算法的数量级。小结