算法分析解析与设计2016-第1讲.ppt

《算法分析解析与设计2016-第1讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计2016，计算机科学与技术硕士研究生第一章算法分析技术什么是算法:看上去与程序的定义相同。说清楚难，随着时代进步,也可以从更多的角度认识算法。维基百科是程序吗？是计算思想吗？要从几个方面描述才行。(1)面对的问题不能太平凡，(2)面对的问题不能太复杂，(3)面对的问题要明确，输入输出数据形式化，(4)在现代数字计算机上能实现。(5)所以要描述成一条一条的语句。算法+数据结构=程序第一章算法分析技术为什么要设计程序，因为要处理信息。为什么要设计算法，因为要解决问题。问题就是描述让计算机干啥？(1)问题；不是一般的问题，

2、有意义的问题，凭感觉了。算法是针对问题的算法，没有问题，哪有算法？(2)算法是程序，又不是程序。计算机语言描述的计算机求解问题的步骤，按照规定的步骤运行可以得到正确的结果。数据结构+算法？=程序例子：求1+2+3+……+n可以编一个程序也可以用公式计算：Sum=0;Fori=1tonSum=Sum+i;EndforOutputSum也可以用公式计算：一步就完成Sum=n*(n+1)/2OutputSum勉强称为算法称为算法太勉强§1.1算法及复杂性算法从何入手，求解问题。计算机干什么？问题：什么是问题，怎么描述，日常生活中的问题描

3、述，就是要让计算机干什么。输入，输出。两个要素:输入和输出，要有严格的描述。实例：描述问题的所有参量。输入数据包含哪些参量询问：陈述问题所求的解的格式和解应满足的性质。问题是告诉人的，不是告诉计算机的。Instance注意，计算机每次求解只是针对一个实例求解，问题的描述针对所有实例，给一个统一的描述。算法：对每个问题实例计算机都能计算出满足询问条件的正确答案，的计算方法。是一个过程，语句集合，语句有次序，按照次序执行语句，处理实例，得到正确答案。对每个实例都能得到正确答案。算法可以理解为一种计算方法，但这种方法一定能用计算机来计算

4、，能用程序实现。程序：算法在计算机上的具体实现。算法与程序没有本质区别，算法一般不关心在哪台计算机上运行。程序关心。例子：求xn，求幂问题实例(Instance)：实数x和正整数n询问(query)：xn=?n=10，x=2016.0913,求：2016.091310每次计算x和n都不同，都是一个实例。方法：算法，[1]x*x*x*x*x*x*x*x*x*x[2]y=x*x,z=y*y,w=z*z,x10=y*w[3][(x*x)2*x]2方法1，2，3分别作9，4，4次乘法。考虑算法的总操作次数，*这个总操作次数称为算法的时间复

5、杂度，或称为算法时间复杂性。什么是基本操作，就看个人怎么想(定义)了。具体情况，具体分析。一个算法所需要的存储单元数目称为算法的空间复杂度，算法1，2，3的空间复杂度分别为2，4，2。算法3的计算：两个变量，y=x*x；y=y*y；y=y*x；y=y*y。时间复杂度和空间复杂度，不能太精确，没法太精确。因为相同的方法，两个人编出不同程序，同一个人两个时刻也编出不同程序。肯定不会完全相同。给出一个界限来表达，表达算法时间复杂性的增长趋势。另外当实例规模很小时，说明算法时间复杂度和空间复杂度意义不大。怎么说明实例规模大时时间复杂度有意

6、义。默认时间复杂度一定是实例规模的函数，实例规模逐渐增大，时间复杂度也增大，因此只要描述时间复杂度随着实例规模增大而增大的增长率，就可以了。如果输入数据需要n个符号，算法的时间复杂度至少需要n个时间单位。x1,x2,x3,………,xn先看这个例子，把刚才的算法推广到一般情况：算法3推广到一般如何：想一种通用的办法。n=(bm-1bm-2…b1b0)2n=(10)2,n=(100)2,n=(1000)2,n=(11000)2,n=(10100)2x8=(((x)2)2)2，n=(1000)2X16+4=((((x)2)2x)2)2,

7、n=(10100)2X16+8=((((x)2x)2)2)2,n=(11000)2X32+16+4=(((((x)2x)2)2x)2)2,n=(110100)2X32+16+8+4=？1begin/n的m位2进制数为n=(bm-1bm-2…b1b0)22y=x3fori=m-2downto0do4begin5y=y*y6Ifbi==1theny=y*x7end8end例子：n=(45)10=(101101)2,x45=x32+8+4+1(((((x)2)2x)2x)2)2x1算法的空间复杂度为2。2也不是太对，随着y增大，所需存储

8、位越来越多。真正用于存储求计算数值的就两个空间单元。若n=100…0，则T(n)=log2n=m-1，若n=111…1，则T(n)=2log2n=2(m-1)所以可以给出时间复杂度的界，log2nT(n)2log2n算法的时间复