算法分析的原理

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

1、1.实现和经验分析不论是去解决一个其他方法不能解决的大规模问题，还是为系统的关键部分提供一种高效的实现，为了高效地利用算法，都需要理解算法的性能特征。理解算法的性能特征的第一步是进行经验分析：经验分析面临的第一个挑战是开发一个正确、完整的算法实现（因此，有可能希望在投入更大精力实现该算法之前，对类似的程序进行数序分析或经验分析）；第二个挑战是确定输入数据的特性，以及对进行的实验冇直接影响到其他因素。典型地，我们有三个基木选择：利用实际数据，随机数据或伪数据。实际数据可以测试程序的真正开销；随机数据确保实验测试的是算法，而不是测试数据；伪数据确保程序可以处理可能的

2、任何输入。对于算法的性能特征，最常犯的错误是忽略了算法的性能特征（即常常接受一个慢速算法而不愿意去处理更复杂的算法）和过多地关注算法的性能特征（如果一个程序只运行几微妙，把这个程序运行时间改进10倍意义并不大）。2.算法分析（数学分析）我们对算法进行数学分析的目的是：•比较同一任务的不同算法；•预测算法在新环境下的能力；•设置算法中的参数值。算法分析的基本步骤：a.明确算法基于的抽彖操作，从而从实现小把分析分离出来；b.研究数据，为算法的输入建立模型；通常考虑以下方法：一是假设输入是随机的，然后研究程序在均匀分布下的性能；二是寻求伪输入，然后研究程序在最坏情况下

3、的性能。3.函数的增长（常用的描述算法性能特征的数学函数）算法的运行时间一般会与以卜•某个函数成止比：1一个程序的所有指令只执行一次或者之多只执行几次，此时程序的运行时间为常量。logN当程序的运行时间为对数是，程序随N的增长而稍微增长。通常在求解一个大规模问题的程序中，它把问题变成一些小的子问题，每一步都把问题的规模缩小儿分之儿，就会岀现这样的运行时间。N当程序的运行时间为线性时，通常对每个输入元素只做了少量的处理工作。这种情况对于一个必须处理N个输入（或产生N个输出）的算法是最优的。NlogN当把问题分解成小问题，且独立求解只问题，然后把这些子问题好的解组合

4、成原有问题的解时，会出现NlogN的运行时间。N2当算法的运行吋间为平方时，算法只适用于规模相对较小的问题。二次运行时间一般出现在需要处理所有数据项对（也许是双层嵌套循环）的算法屮。N3类似地，处理三个数据项的算法（或许是三层嵌套循环）的运行时间为立方，这样的算法只适用于小规模的问题。2N一个指数运行吋间的算法很难在实际中使用。其余常用函数和常数:函数名称特殊值近似LxJfloor函数L3.14J=3X仪1ceil函数[3.141=4XIgN以2为底的对数lgl024=101.441nNFn斐波那契数F10=55(pN/V5hn调和数H10匕2.9InN+yN!

5、阶乘函数101=3628800(N/e)Nlg(N!)]g(100!)«520NlgN-1.44Ne=2.71828…Y=0.57721…(欧拉常数)2,F0=O.Fi=1两个相邻的斐波那契数列的比例接近黄金

6、分割比率。阶乘表示了N个对象的所有排列。二项分布及泊松分布：1.大0分布定义：如果存在常数Co和No,对于所有N〉N°,有g(N)〈C°f(N),则称函数g(N)是O(f(N))的。大0符号有三个作用：•限制忽略数学公式中的低阶项时产生的误差；•限制曲于忽略对程序的总运行时间贡献较小的某些部分时产生的错误；•允许我们按照算法总运行时间的上界对算法进行分类。大0符号允许我们在操作近似数学表达式时，只记录首项，而可以忽略其他低阶项，最终可使我们给出对于所分析的数学表达式的精确近似的简洁陈述。如果函数f(N)渐近大于另一个函数g(N)(即当N-00时,g(N)/f(N

7、)->0),我们有时用约等于f(N)表示f(N)+0(g(N))o比如N(N-l)/2,我们可以近似表示为N2/2O类似地，如果我们能够证明当g(N)渐近小于f(N)时，算法的运行时间of(N)+g(N),则说算法的运行时间与f(N)成正比。1.基本递归方程公式如果程序的循环通过输入每次减少一项，递归公式为：CN=Cn“+N,N>2,.RCi=1其解为Cn约等TN2/2O公式2：如果程序毎次使输入减半，递归公式为：Cn=Cn/2+1,N>2,且C]=1其解为Cn约等于IgN。公式3：如果程序每次使输入减半，但需要检杳输入的每一项，递归公式为：其解为Cn约等于2N

8、。公式4：如果程序把输入