朱大鸣全套配套课件算法分析与设计 算法设计与分析-1.ppt

《朱大鸣全套配套课件算法分析与设计 算法设计与分析-1.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章算法分析技术§1.1算法及复杂性算法从何入手，求解问题。计算机干什么？将所有想让计算机干的事全部描述成问题。问题：什么是问题，怎么描述，日常生活中的问题描述，实际就是要让计算机干什么。输入，输出。两个要素:输入输出，要有严格的描述。实例：描述问题的所有参量。询问：陈述问题所求的解的格式和解应满足的性质。注意，计算机每次求解只是针对一个实例求解，问题的描述针对很多实例，通用的描述。算法：对每个问题实例计算机都能计算出满足询问条件的正确答案，的计算方法。是一个过程，语句集合，语句有顺序，按照顺序执行语句，处理实例，得到正确答案。一种计算方法。对每个实例计算都能

2、得到正确答案。程序：算法的形式描述。例子：求xn，求幂问题实例(instance)：实数x和正整数n询问(query)：xn=?n=10，求：x10每次计算x和n都不同，都是一个实例。方法：算法，1x*x*x*x*x*x*x*x*x*xy=x*x,z=y*y,w=z*z,x10=y*w3[(x*x)2*x]2方法1，2，3分别作9，4，4次乘法。考虑算法的总操作次数.*这个总操作次数称为算法的时间复杂度，或称为算法时间复杂性。一个算法所需要的存储单元数目称为算法的空间复杂度，算法1，2，3的空间复杂度分别为2，4，2。算法3的计算：两个变量，y=x*x；y=y*

3、y；y=y*x；y=y*y。时间复杂度和空间复杂度，不能太精确，没法太精确。因为相同的方法，两个人编出不同程序，同一个人两个时刻也编出不同程序。肯定不会完全相同。给出一个数量级来表达，数量级的参数是什么。实际只能用一个界表示。算法3推广到一般如何：想一种通用的办法。1begin/n的m位2进制数为bm-1bm-2…b1b02y=x3fori=m-2downto0do4begin5y=y*y6Ifbi==1theny=y*x7end8end例子：n=(11)10=(1011)2算法的空间复杂度为2。2也不是太对，随着y增大，所需存储位越来越大。真正用于存储求计算数

4、值的就两个空间。若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§1.2渐进估计技术及基本规则在算法分析时，十分关心算法时间复杂度或空间复杂度的增长率，并不十分关心算法时间复杂度的具体值。时间复杂度不会比空间复杂度大。算法时间复杂度随着实例规模增大而增大

5、。问题规模怎样表示？每个问题都有一个参量说明问题的规模。两个符号：O(*)，(*)1若存在n0和C，使当n>n0时，T(n)Cf(n)，则称T(n)=O(f(n))如，T(n)=(1+n)2=O(n2)T(n)=2n3+4n2=O(n3)O(f(n))描述算法时间复杂度的上界，说明算法好时往往用O(f(n))。2存在常数C，使n无穷大时，T(n)Cg(n)，则记为：T(n)=(g(n))如：T(n)=2n+(3/2)n=(2n)，可以写成O(2n)吗？T(n)=可以写成：T(n)=(n2)吗，O(n2)，O(n)，(n)例1.2排序算法，将数组中的

6、数据排列成递增次序：Procedurebubble(A[1-n]ofinteger)Begin1fori=1ton-12forj=ndowntoi+1do3ifA[j-1]>A[j]then4begin5temp=A[j-1]6A[j-1]=A[j]7A[j]=temp8end9end时间复杂度分析，考虑最坏情况。有时比较完成以后要交换，有时不要交换，比较一次，交换3次。第一遍比较n-1次，第二遍比较n-2次，…………。时间复杂度。只算比较次数：T(n)=(n-1)+(n-2)+…+2+1=n(n-1)/2=O(n2)细算比较多少次，交换多少次？§1.3递归算法

7、分析例子：合并排序Functionmergesort(L:listofinteger,n)BeginIfn==1thenreturnLElsebeginbreakLintoL1andL2,eachoflengthL/2return(merge(mergesort(L1,n/2),mergesort(L2,n/2)))endend时间复杂度分析，两个n/2长的表合成一个表，需要O(n)次。T(n)=求出T(n)需要解递推方程。解递推方程的3种方法：1猜测法，2展开法，3求解法上述方程：猜测T(n)=O(nlogn)anlogn+b,a,b为常数，下面证明.当n=

8、1时，猜测成立设nk时