数据结构概述.ppt

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

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

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

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

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

5、：逐个选择最小数据逐个选择最小数据逐个选择最小数据逐个选择最小数据算法框架：算法框架：算法框架：算法框架：for(for(intint 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 算法设计过程算法设计过程 自顶向下，逐步求精自顶向下，逐步求精 void selec

6、tSort(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;第一个层次第一个层次程序不包含语法错误程序不包含语法错误intint sign(intsign(int x)x)inti

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

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

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

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

11、进行测试；：模拟数据进行测试；n在算法中的某些部位插装时间函数在算法中的某些部位插装时间函数 time()或者或者clock()测定算法完成某一功能所花费的时间。测定算法完成某一功能所花费的时间。n采用开发工具提供的时间测量工具采用开发工具提供的时间测量工具profile算法的后期测试算法的后期测试顺序搜索顺序搜索顺序搜索顺序搜索(SequenialSequenial Search Search)行行行行 intint seqsearchseqsearch (intint a a,const const intint n,n,const const intint x x)/a a0,0,a,a

12、 n n-11 1 1 2 2 intint i=i=0 0;3 3 whilewhile(i i n n&a a i i!=x=x)4 4 i+i+;5 5 if if(i=ni=n)returnreturn -1 1;6 6 returnreturn i i;7 7 插装插装插装插装 clockclock()()的计时程序的计时程序的计时程序的计时程序 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);for(j=0;j 20;j+)clock_t start,stop;start=clock start=clock()();long long count=500000count=500000;whilewhile(count(count-)-)int k=seqsearch(a,1001,1001,n n j j);stop=stop=clockclock()();double runTim

14、e=stop =stop startstart;printf(“%12d%12d%12.6fn”,nj,runTime,double(runTime)/500000);double(runTime)/500000);程序测试结果输出程序在计算机上运行所需时间的影响因素程序在计算机上运行所需时间的影响因素程序在计算机上运行所需时间的影响因素程序在计算机上运行所需时间的影响因素算法本身选用的策略算法本身选用的策略算法本身选用的策略算法本身选用的策略问题的规模问题的规模问题的规模问题的规模规模越大，消耗时间越多规模越大，消耗时间越多规模越大，消耗时间越多规模越大，消耗时间越多书写程序的语言书写程序的

15、语言书写程序的语言书写程序的语言语言越高级，消耗时间越多语言越高级，消耗时间越多语言越高级，消耗时间越多语言越高级，消耗时间越多编译产生的机器代码质量编译产生的机器代码质量编译产生的机器代码质量编译产生的机器代码质量机器执行指令的速度机器执行指令的速度机器执行指令的速度机器执行指令的速度为便于比较算法本身的优劣为便于比较算法本身的优劣应排除其它影响算法效率的因素应排除其它影响算法效率的因素希望软件执行时间可预测希望软件执行时间可预测 算法分析算法分析感兴趣的不是具体的资源占用量，而是与具体感兴趣的不是具体的资源占用量，而是与具体的平台无关、具体的输入实例无关，且随着规模增长的的平台无关、具体的

16、输入实例无关，且随着规模增长的值是可预测的。值是可预测的。算法的事前估计算法的事前估计算法的事前估计算法的事前估计希望了解软件执行时间的变化趋势希望了解软件执行时间的变化趋势 与问题与问题规模之间的关系，用一定的规模数据作为输入时规模之间的关系，用一定的规模数据作为输入时程序所需的基本操作的次数来描述时间效率程序所需的基本操作的次数来描述时间效率忽略细节忽略细节 完成完成一个基本操作所需要的时间应该与具体的被操作数一个基本操作所需要的时间应该与具体的被操作数无关无关 算法的复杂性分析算法的复杂性分析例例 以迭代方式求累加和的函数以迭代方式求累加和的函数行行 float sum(float a,

17、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 插入计数全局变量插入计数全局变量countw w 建表，列出个语句的程序步建表，列出个语句的程序步建表，列出个语句的程序步建表，列出个语句的程序步计算计算累加和累加和程序程序程序步数程序步数计算工作表格计算工作表格 语句执行的频度语句执行的频度语句执行的频度语句执行的频度 2n+32n+3程序的精确步数没有实际意义，程序步数的数量级别可以程序的精确步数没有实际意义，程序步数的数量级别可以反映程序的实质。反映程序的实质。n：一

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

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

20、大小比较来考虑，当n n增到到一定值后，对资源开增到到一定值后，对资源开增到到一定值后，对资源开增到到一定值后，对资源开销影响最大的就是销影响最大的就是销影响最大的就是销影响最大的就是n n的幂次最高的项，所以使用的幂次最高的项，所以使用的幂次最高的项，所以使用的幂次最高的项，所以使用Big-OhBig-Oh表示表示表示表示法时不必考虑法时不必考虑法时不必考虑法时不必考虑常数、系数、次要项和关系常数、系数、次要项和关系常数、系数、次要项和关系常数、系数、次要项和关系符号符号符号符号。O(nO(n2 2)O(2nO(2n2 2+2n+1)+2n+1)n n常见的算法时间复杂度：常见的算法时间复杂

21、度：常见的算法时间复杂度：常见的算法时间复杂度：1 log2n n nlog2n n2 n3 2n 3n n!n n算法时间复杂度的分析规则算法时间复杂度的分析规则算法时间复杂度的分析规则算法时间复杂度的分析规则 按照程序的结构分析时间复杂度按照程序的结构分析时间复杂度按照程序的结构分析时间复杂度按照程序的结构分析时间复杂度时间复杂度的渐进表示法加法规则加法规则 针对并列程序段：顺序结构，针对并列程序段：顺序结构，if结构，结构，switch结构结构 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)乘法规则乘法规则 针对嵌套程序段；针对嵌套程序段；for，while，dow

22、hile T(n,m)=T1(n)*T2(m)=O(f(n)*g(m)时间复杂度计算例例例例1 1：x+;s=0;x+;s=0;用频度法分析：将用频度法分析：将用频度法分析：将用频度法分析：将x+x+看成是基本操作，语句频度为看成是基本操作，语句频度为看成是基本操作，语句频度为看成是基本操作，语句频度为T(nT(n)=2)=2算法的时间复杂度：算法的时间复杂度：算法的时间复杂度：算法的时间复杂度：O(1)-O(1)-常量阶常量阶常量阶常量阶例例例例2:for(i=0;in;i+)2:for(i=0;in;i+)/执行执行执行执行n+1n+1次次次次 x+;/x+;/语句频度为：语句频度为：语句

23、频度为：语句频度为：n n s+=x;/s+=x;/语句频度为：语句频度为：语句频度为：语句频度为：n n T(nT(n)=2n+n+1=3n+1)=2n+n+1=3n+1，则时间复杂度为：，则时间复杂度为：，则时间复杂度为：，则时间复杂度为：O(nO(n)也可以这样考虑：将也可以这样考虑：将也可以这样考虑：将也可以这样考虑：将x x自增看成是基本操作，则语句频度为：自增看成是基本操作，则语句频度为：自增看成是基本操作，则语句频度为：自增看成是基本操作，则语句频度为：n n其其其其时间复杂度为：时间复杂度为：时间复杂度为：时间复杂度为：O(nO(n)，即时间复杂度为线性阶。，即时间复杂度为线性

24、阶。，即时间复杂度为线性阶。，即时间复杂度为线性阶。例例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 3)计算方法计算方法1 1：由于是一个三重循环，每个循环从由于是一个三重循环，每个循环从1 1到到n n，则总次数为，则总次数为:nnnnnn=n=n3 3 故时间复杂度为故时间复杂度为T(nT(n)=O(n)=O(n3 3

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

26、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 时间复杂度计算算法中基本操作重复执行的次数随问题的输入数据集不同而不同算法中基本操作重复执行的次数随问题的输入数据集不同而不同例例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=

27、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(nT(n)=(1+2+.+)=(1+2+.+n)/nn)/n算法的时间复杂度：算法的时间复杂度：O(nO(n)1-28 时间复杂度按数量递增排列及增长率一个算法时间为一个算法时间为O(1)O(1)的算法，它的基本运算执行的次数是固定的

28、。的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为为O(nO(n2 2)的算法则由一个二次多项式来限界。的算法则由一个二次多项式来限界。以下六种计算算法时间的多项式是最常用的。其关系为：以下六种计算算法时间的多项式是最常用的。其关系为：O(1)O(log 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

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

30、、简单变量、定长成分(如数如数如数如数组元素、结构成分、对象的数据成员等组元素、结构成分、对象的数据成员等组元素、结构成分、对象的数据成员等组元素、结构成分、对象的数据成员等)变量所占的空间变量所占的空间变量所占的空间变量所占的空间 可变部分可变部分可变部分可变部分尺寸与实例特性有关的成分变量所占空间、引用变量所尺寸与实例特性有关的成分变量所占空间、引用变量所尺寸与实例特性有关的成分变量所占空间、引用变量所尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、递归栈所用的空间、通过占空间、递归栈所用的空间、通过占空间、递归栈所用的空间、通过占空间、递归栈所用的空间、通过newnew和和和和d

31、eletedelete命令动态命令动态命令动态命令动态使用使用使用使用的空间的空间的空间的空间 空间复杂度的度量空间复杂度的度量空间复杂度的度量空间复杂度的度量 只考虑程序使用的可变部分空间使用情况只考虑程序使用的可变部分空间使用情况只考虑程序使用的可变部分空间使用情况只考虑程序使用的可变部分空间使用情况空间复杂度度量渐进的空间渐进的空间渐进的空间渐进的空间复杂度复杂度复杂度复杂度n n一个算法为解决问题所用辅助存储空间的大小，只依赖一个算法为解决问题所用辅助存储空间的大小，只依赖一个算法为解决问题所用辅助存储空间的大小，只依赖一个算法为解决问题所用辅助存储空间的大小，只依赖于问题的规模（通常

32、用整数量于问题的规模（通常用整数量于问题的规模（通常用整数量于问题的规模（通常用整数量n n表示），即它是问题规表示），即它是问题规表示），即它是问题规表示），即它是问题规模的函数。模的函数。模的函数。模的函数。算法的渐进空间复杂度，简称算法空间复杂度记作：算法的渐进空间复杂度，简称算法空间复杂度记作：算法的渐进空间复杂度，简称算法空间复杂度记作：算法的渐进空间复杂度，简称算法空间复杂度记作：S(n)=O(f(n)S(n)=O(f(n)表示最坏情况下，算法所需辅助存储空间的数量是实例表示最坏情况下，算法所需辅助存储空间的数量是实例表示最坏情况下，算法所需辅助存储空间的数量是实例表示最坏情况下，

33、算法所需辅助存储空间的数量是实例特性特性特性特性n n的某个函数的数量级，表示所需存储空间增长的的某个函数的数量级，表示所需存储空间增长的的某个函数的数量级，表示所需存储空间增长的的某个函数的数量级，表示所需存储空间增长的数量级。数量级。数量级。数量级。例例解法解法解法解法1 1 1 1 先计算先计算先计算先计算x x x x 的幂的幂的幂的幂,存于存于存于存于power power power power 中中中中,再分别乘以相应的系数再分别乘以相应的系数再分别乘以相应的系数再分别乘以相应的系数#define N 100#define N 100float evaluate(float fl

34、oat evaluate(float coefcoef,float x,float x,intint n)n)float powerN,f;float powerN,f;intint i;i;for(power 0=1,i=1;i=n;i+)for(power 0=1,i=1;i=n;i+)poweripoweri=x*poweri-1;=x*poweri-1;for(f=0,i=0;i=N;i+)for(f=0,i=0;i=0;i-),i=n-1;i=0;i-)f=f*f=f*x+coefix+coefi;return(f);return(f);时间复杂度为时间复杂度为时间复杂度为时间复杂度

35、为O(n).O(n).空间复杂度为空间复杂度为空间复杂度为空间复杂度为O(1)O(1)n算法是对于问题解决步骤的描述，是一个指令的系列；算法是对于问题解决步骤的描述，是一个指令的系列；n算法具有确定性、有穷性、有效性；算法具有确定性、有穷性、有效性；n算法的评价可以从正确、可读、健壮和效率四个方面进行算法的评价可以从正确、可读、健壮和效率四个方面进行评价好坏；评价好坏；n算法的效率可以从运行时间和运行时所用的空间开销进行算法的效率可以从运行时间和运行时所用的空间开销进行评价；评价；n绝对的时间和空间开销即难以获取，有不能准确反映程序绝对的时间和空间开销即难以获取，有不能准确反映程序的实质，所以一般对效率的度量采用事前分析的方法，即的实质，所以一般对效率的度量采用事前分析的方法，即根据算法处理的步骤，得到算法的渐进时间复杂度和算法根据算法处理的步骤，得到算法的渐进时间复杂度和算法的渐进空间复杂度描述，从而确定算法的时空需求随问题的渐进空间复杂度描述，从而确定算法的时空需求随问题规模的变化趋势，从而可以确定算法的数量级。规模的变化趋势，从而可以确定算法的数量级。小结