《算法分析和计算复杂性分析》由会员分享，可在线阅读，更多相关《算法分析和计算复杂性分析（13页珍藏版）》请在金锄头文库上搜索。
1、算法分析与评估1概述在查找引擎优化范畴里边有一个疑问常常让人感受捉摸不透到底是什么样的排序要素 结尾决定了网页的排名。而每个查找引擎公司都将其的查找引擎算法维护的极端严密，只有 很少很少的一些的公司能有时机看到这些算法的全貌。并且就算是有时机看到这些算法的真 实容貌，要想领悟到话，还得具有深沉的数学功底。这使得对查找引擎优化整个概念的晓得 变得很艰难。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的 效率。个算法得出一个解，那么这个解是最优解还是可行解？如果是可行解，与最优解的偏 差有多大？对于算法的效果，存在两种评价方法一一证明方法和仿真分析方法。证明方法是 指利用数学方
2、法对于算法进行评估，证明它的解的类型。仿真分析方法是指产生或选取大量 的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进 行统计分析。例如对于TSP问题贪心算法的模拟与分析，关于贪心算法的正确性，直观上只需检查 算法的输出结果中，每个城市出现且只出现一次，该结果即是TSP问题的可行解，说明算 法正确的求解了这些问题。关于它的效果，如果实例的最优解一直（问题规模小或问题已被 成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进 行效果评价。而对于较大规模的问题实例，其最优解往往是未知的，因此算法的效果评价 只能借助于与前人算法的结果的比较
3、。2复杂度评价一个算法时另一个问题是 算法能够执行的了吗？有限的时间和空间上这个算法能 够执行吗？这就需要对算法的复杂性进行分析。算法的时间复杂度和空间复杂度合称为算法 的复杂度。2.1 时间复杂度(1 )时间频度一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运 行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费 的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行 次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数 称为语句频度或时间频度。记为T(n)。(2 )时间复杂度在刚才提到的时间频度中
4、，n称为问题的规模，当n不断变化时，时 间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时 间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数， 用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T( n)/f(n)的极限值为不等 于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n),称0(f(n)为算法的渐进 时间复杂度，简称时间复杂度。时间频度不同，但时间复杂度可能相同。如：T(n)=n2+3n+4与T(n)=4n2+2n+1它们的 频度不同，但时间复杂度相同，都为0(n2)。按数量级递增排列
5、，常见的时间复杂度有：常数阶0(1)，对数阶O(log2n),线性阶0(n), 线性对数阶0(nlog2n),平方阶0(n2),立方阶0(n3),. ,k次方阶0(nk),指数阶0(2n)。随着 问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。(3) 最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称最坏时间复杂 度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是： 最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界这就保证了算法的运行 时间不会比任何更长。在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例，该算法的运
6、行时间 不可能大于0(n)。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算 法的期望运行时间。指数阶0(2n)，显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无 法应用。(4) 求时间复杂度【1】如果算法的执行时间不随着问题规模n的增加而增长即使算法中有上千条语句， 其执行时间也不过是一个较大的常数。此类算法的时间复杂度是0(1)。x=91;y=100;while(y0) if(x100) x=x-10;y-; else x+;解答：T(n)=O(1)，这个程序看起来有点吓人，总共循环运行了 1100次，但是我们看到n没有？没。这段程序的运行是和n无关的，就算
7、它再循环一万年，我们也不管他，只是一个常数阶的函数【2】当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内 层语句的频度f(n)决定的。x=1;for(i=1;i=0&(Ai!=k)i-;return i;此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及 K的取值有关：若A中没有与K相等的元素，则语句(3)的频度f(n)=n ;若A的最后一 个元素等于K,则语句(3)的频度f(n)是常数0。(5) 时间复杂度评价性能有两个算法A1和A2求解同一问题 时间复杂度分别是T1(n)=100n2 T2(n)=5n3( 1 ) 当输入量nT2(n)，后者
8、花费的时间较少。(2)随着问题规模n的增大， 两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比 算法A2要有效地多。它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在 时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而 经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)般是算法中频度最 大的语句频度。2.2 空间复杂度一个程序的空间复杂度是指运行完一个程序所需内存的大小。利用程序的空间复杂度， 可以对程序的运行所需要的内存多少有个预先估计。一个程序执行时除了需要存储空间和存 储
9、本身所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和 存储一些为现实计算所需信息的辅助空间。程序执行时所需存储空间包括以下两部分。（1）固定部分。这部分空间的大小与输刀输出的数据的个数多少、数值无关。主要包 括指令空间（即代码空间）数据空间（常量、简单变量）等所占的空间。这部分属于静态 空间。（2）可变空间，这部分空间的主要包括动态分配的空间，以及递归栈所需的空间等。 这部分的空间大小与算法有关。一个算法所需的存储空间用f（n）表示。S（n）=O（f（n）其中n为问题的规模，S（n）表示空间复杂度。3对几种排序算法进行分析3.1、冒泡法（起泡法）3.1.1算法要求：用
10、起泡法对10个整数按升序排序。3.1.2算法分析：如果有n个数，则要进行n-1趟比较。在第1趟比较中要进行n-1次 相邻元素的两两比较，在第j趟比较中要进行n-j次两两比较。比较的顺序从前往后，经过 趟比较后，将最值沉底（换到最后一个元素位置），最大值沉底为升序，最小值沉底为降 序。3.1.3算法源代码：# in elude mai n()int a10,i,j,t;prin tf(Please in put 10 nu mbers:);/*输入源数据*/for(i=0;i10;i+)sca nf(%d,&ai);/*排序*/for(j=0;j9;j+)/*外循环控制排序趟数，n个数排n-1趟
11、*/for(i=0;iai+1)/*相邻元素比较，逆序则交换*/ t=ai;ai=ai+1;ai+1=t;/*输出排序结果*/prin tf(The sorted nu mbers:);for(i=0;i10;i+)prin tf(%d ,ai);prin tf(n);3.1.4算法特点：相邻元素两两比较，每趟将最值沉底即可确定一个数在结果的位置， 确定元素位置的顺序是从后往前，其余元素可能作相对位置的调整。可以进行升序或降序排 序。3.1.5优点：稳定，比较次数已知；3.1.6缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。3.2、选择法3.2.1算法要求：用选择法对10个整数按降序排
12、序。3.2.2算法分析：每趟选出一个最值和无序序列的第一个数交换，n个数共选n-1趟。 第i趟假设i为最值下标，然后将最值和i+1至最后一个数比较，找出最值的下标，若最值 下标不为初设值，则将最值元素和下标为i的元素交换。3.2.3算法源代码：# in elude mai n()int a10,i,j,k,t ,n=10;prin tf(Please in put 10 nu mbers:);for(i=0;i10;i+)sca nf(%d,&ai);for(i=0;in-1;i+)/*外循环控制趟数，n个数选n-1趟*/k=i;/*假设当前趟的第一个数为最值，记在k中*/for(j=i+1;
13、j n ;j+)/*从下一个数到最后一个数之间找最值*/if(akaj)/*若其后有比最值更大的*/k=j;/*则将其下标记在k中*/if(k!=i)/*若k不为最初的i值，说明在其后找到比其更大的数*/ t=ak; ak=ai; ai=t; /*则交换最值和当前序列的第一个数7prin tf(The sorted nu mbers:);for(i=0;i10;i+)prin tf(%d ,ai);prin tf(n);3.2.4算法特点：每趟是选出一个最值确定其在结果序列中的位置，确定元素的位置是 从前往后，而每趟最多进行一次交换，其余元素的相对位置不变。可进行降序排序或升序排 序。3.2.
14、5优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少；3.2.6缺点：相对之下还是慢。3.3、插入法3.3.1算法要求：用插入排序法对10个整数进行降序排序。3.3.2算法分析：将序列分为有序序列和无序列，依次从无序序列中取出元素值插入到 有序序列的合适位置。初始是有序序列中只有第一个数，其余n-1个数组成无序序列，则n 个数需进n-1次插入。寻找在有序序列中插入位置可以从有序序列的最后一个数往前找，在 未找到插入点之前可以同时向后移动元素，为插入元素准备空间。3.3.3算法源代码：# in elude main ()int a10,i,j,t;prin tf(Please in put 10 nu mbers:);for(i=0;i10;i+)sca nf(%d,&ai);for(i=1;i10;i+)/*外循环控制趟数，n个数从第2个数开始到最后共进行n
