算法分析与设计-朱大鸣-算法设计与分析-1.ppt

第一章算法分析技术
§ 算法及复杂性
算法从何入手,求解问题。
计算机干什么?将所有想让计算机干的事全部描述成问题。
问题:什么是问题,怎么描述,日常生活中的问题描述,实际就是要让计算机干什么。输入,输出。
两个要素:输入输出,要有严格的描述。
实例:描述问题的所有参量。
询问:陈述问题所求的解的格式和解应满足的性质。
注意,计算机每次求解只是针对一个实例求解,问题的描述针对很多实例,通用的描述。
算法:对每个问题实例计算机都能计算出满足询问条件的正确答案,的计算方法。是一个过程,语句集合,语句有顺序,按照顺序执行语句,处理实例,得到正确答案。一种计算方法。对每个实例计算都能得到正确答案。
程序:算法的形式描述。
例子:求xn,求幂问题
实例(instance):实数x和正整数n
询问(query):xn=?
n=10,求:x10
每次计算x和n都不同,都是一个实例。
方法:算法,
1 x*x*x*x*x*x*x*x*x*x
y=x*x, z=y*y, w=z*z, x10=y*w
3 [(x*x)2*x]2
方法1,2,3分别作9,4,4次乘法。考虑算法的总操作次数.
*这个总操作次数称为算法的时间复杂度,或称为算法时间复杂性。
一个算法所需要的存储单元数目称为算法的空间复杂度,算法1,2,3的空间复杂度分别为2,4,2。
算法3的计算:两个变量,y=x*x;y=y*y;y=y*x;y=y*y。
时间复杂度和空间复杂度,不能太精确,没法太精确。因为相同的方法,两个人编出不同程序,同一个人两个时刻也编出不同程序。肯定不会完全相同。给出一个数量级来表达,数量级的参数是什么。实际只能用一个界表示。
算法3推广到一般如何:想一种通用的办法。
1 begin
/n的m位2进制数为bm-1bm-2…b1b0
2 y=x
3 for i=m-2 down to 0 do
4 begin
5 y=y*y
6 If bi==1 then y=y*x
7 end
8 end
例子:n= (11)10=(1011)2
算法的空间复杂度为2。2也不是太对,随着y增大,所需存储位越来越大。真正用于存储求计算数值的就两个空间。
若n=100 … 0,则T(n)=log2n,若n=111…1,则T(n)=2log2n
算法的时间复杂度随着n的增大而增大,要考虑算法时间复杂度T(n)的随着n的增长率。n是x的个数。
真正讨论算法时间复杂度时,总关心算法时间复杂度随着实例规模增大而增大的数量级。
上述算法的时间复杂度显然跟实例有关,也跟n有关。满足:
log2nT(n)2log2n
§ 渐进估计技术及基本规则
在算法分析时,十分关心算法时间复杂度或空间复杂度的增长率,并不十分关心算法时间复杂度的具体值。时间复杂度不会比空间复杂度大。
算法时间复杂度随着实例规模增大而增大。问题规模怎样表示?每个问题都有一个参量说明问题的规模。