算法分析及计算复杂性分析

《算法分析及计算复杂性分析》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析与评估1.概述在查找引擎优化范畴里边有一个疑问常常让人感受捉摸不透，到底是什么样的排序要素结尾决定了网页的排名。而每个查找引擎公司都将其的查找引擎算法维护的极端严密，只有很少很少的一些的公司能有时机看到这些算法的全貌。并且就算是有时机看到这些算法的真实容貌，要想领悟到话，还得具有深沉的数学功底。这使得对查找引擎优化整个概念的晓得变得很艰难。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。一个算法得出一个解，那么这个解是最优解还是可行解？如果是可行解，与最优解的偏差有多大？对于算法的效果，存在两种评价方法——证明

2、方法和仿真分析方法。证明方法是指利用数学方法对于算法进行评估，证明它的解的类型。仿真分析方法是指产生或选取大量的、具有代表性的问题实例，利用该算法对这些问题实例进行求解，并对算法产生的结果进行统计分析。例如对于TSP问题贪心算法的模拟与分析，关于贪心算法的正确性，直观上只需检查算法的输出结果中，每个城市出现且只出现一次，该结果即是TSP问题的可行解，说明算法正确的求解了这些问题。关于它的效果，如果实例的最优解一直（问题规模小或问题已被成功求解），利用统计方法对若干问题实例的算法结果与最优解进行对比分析，即可对其进行效果评价。而对于较大规模的问题

3、实例，其最优解往往是未知的，因此，算法的效果评价只能借助于与前人算法的结果的比较。2•复杂度评价一个算法时另一个问题是，算法能够执行的了吗？有限的时间和空间上这个算法能够执行吗？这就需要对算法的复杂性进行分析。算法的时间复杂度和空间复杂度合称为算法的复杂度。2.1•时间复杂度(1)时间频度一个算法执行所耗费的时间，从理论上是不能算岀来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，

4、它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)o(2)时间复杂度在刚才提到的时间频度中，门称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),^O(f(n))为算法的渐进时间复杂度，简称时间复杂度。时

5、间频度不同，但时间复杂度可能相同。如:T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为0(n2)o按数量级递增排列，常见的时间复杂度有：常数阶0(1),对数阶O(log2n),线性阶0(n),线性对数阶O(nlog2n),Y方阶0(n2),立方阶O(n3),...,k次方阶O(nk),指数阶O(2n)o随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。(3)最坏时间复杂度和平均时间复杂度最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度

6、。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。在最坏情况下的时间复杂度为T(n)=O(n),它表示对于任何输入实例，该算法的运行时间不可能大于0(n)o平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。指数阶0(2n),显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。(2)求时间复杂度【"如果算法的执行时间不随着问题规模n的增加而增长即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是0(1

7、)。x=91;y=100;while(y>0)if(x>100){x=x-10;y-;}elsex++;解答:T(n)=0(1),这个程序看起来有点吓人，总共循环运行了"00次，但是我们看到n没有？没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数[2]当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。x=1;for(i=1;i<二n;i++)for（j=1；j<=i；j++）for(k=1;k<=j;k++)x++;该程序段中频度最大的语句是(5)内循环的执行

8、次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：则