算法引论精.ppt

《算法引论精.ppt》由会员分享，可在线阅读，更多相关《算法引论精.ppt（36页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法引论第1页，本讲稿共36页时间复杂度计算表示时间复杂度计算表示 假设假设f(n)为某算法的计算时间，为某算法的计算时间，n是问题的大小，是问题的大小，g(n)是事先确定是事先确定的简单函数，如：的简单函数，如：nm，2n，n!。n定义定义1-1如果存在两个正常数如果存在两个正常数c和和n0，对所有，对所有n n0，有，有|f(n)|c|g(n)|则记作：则记作：f(n)=O(g(n),O为数量级（阶数），为数量级（阶数），g(n)是计算时间是计算时间f(n)的一个的一个上界函数上界函数，f(n)的数量级是的数量级是g(n)。定理定理1-1 若若 是一个是一个m次多项式，则次多项式，则证明：

2、证明：（？）（？）说明：变量说明：变量n的阶数为的阶数为m的多项式与其最高阶同阶的多项式与其最高阶同阶。第2页，本讲稿共36页时间复杂度计算表示时间复杂度计算表示定义定义1（2）（下界函数）如果存在两个正常数（下界函数）如果存在两个正常数c和和n0，对所有，对所有nn0，有，有|f(n)|c|g(n)|则记作：则记作：f(n)=(g(n)，g(n)是计算时间是计算时间f(n)的一个的一个下界函数下界函数。定义定义1（3）（双界函数）如果存在两个正常数（双界函数）如果存在两个正常数c1，c2和和n0，对所有，对所有nn0，有，有 则：则：说明：说明：g(n)既是计算时间既是计算时间f(n)的一个

3、下界函数也是一的一个下界函数也是一个上界函数。个上界函数。第3页，本讲稿共36页时间复杂度计算表示时间复杂度计算表示两个函数阶数的比较方法有如下结论：两个函数阶数的比较方法有如下结论：假设假设有下列情况：有下列情况：（1）如果）如果L=a，a是有限正常数，则是有限正常数，则；（2）如果）如果L=0，则，则f(n)的阶数比的阶数比g(n)低（低（)；由此可以得到数量级的大小比较：由此可以得到数量级的大小比较：（多项式时间算法与指数时间算法）（多项式时间算法与指数时间算法）第4页，本讲稿共36页时间复杂度的几个相关问题时间复杂度的几个相关问题问题问题1 算法耗费的时间和语句频度算法耗费的时间和语句

4、频度一个算法耗费的时间一个算法耗费的时间=算法中每条语句的执行时间之和算法中每条语句的执行时间之和每条语句的执行时间每条语句的执行时间=语句的执行次数（语句的执行次数（frequency count）语句执行一次所需时间语句执行一次所需时间n算法转化为程序后，算法转化为程序后，每条语句的执行时间取决于：每条语句的执行时间取决于：机器的指令性能，速度以及编译所产生的代码质量机器的指令性能，速度以及编译所产生的代码质量等难以确定的因素等难以确定的因素n一般分析时是独立于机器的软硬件系统分析算法的复一般分析时是独立于机器的软硬件系统分析算法的复杂性，即设每条语句执行一次的时间均为单位时间杂性，即设每

5、条语句执行一次的时间均为单位时间n一个算法的时间耗费就是该算法中所有语句的频度和一个算法的时间耗费就是该算法中所有语句的频度和第5页，本讲稿共36页例例1-1（矩阵乘法）求两个（矩阵乘法）求两个n阶方阵阶方阵A，B的乘积的乘积CVoidMatrixMultiply(intAnn,intBnn,intCnn)inti,j,k;(1)For(i=0;in;i+)(2)for(j=0;jn;j+)(3)Cij=0;(4)for(k=0;kn;k+)(5)Cij=cij+AikBkj 其渐近时间复杂度：其渐近时间复杂度：，T(n)的数的数量级是量级是n3，即，即T(n)=O(n3)。频度：频度：频度：

6、频度：n+1n+1，循环执行，循环执行，循环执行，循环执行n n次次次次n(n+1)n(n+1)n n2 2n n2 2(n+1)(n+1)n n3 3频度和频度和频度和频度和=n+1+n(n+1)+n=n+1+n(n+1)+n2 2+n+n2 2(n+1)+n(n+1)+n3 3=2n=2n3 3+3n+3n2 2+2n+1=T(n)+2n+1=T(n)第6页，本讲稿共36页问题问题2 用渐近时间复杂度评价算法的时间性能用渐近时间复杂度评价算法的时间性能例例1-2 设有算法设有算法A1和和A2求解同一问题，时间复杂度分别为求解同一问题，时间复杂度分别为 。容易看出容易看出它们的渐近时间复杂度

7、为它们的渐近时间复杂度为O(n2)与与O(n3)，宏观地评价了这两，宏观地评价了这两个算法在时间方面的质量。约定不区分时间复杂度和渐近时间复杂度，个算法在时间方面的质量。约定不区分时间复杂度和渐近时间复杂度，常用渐近时间复杂度评价算法的时间性能。常用渐近时间复杂度评价算法的时间性能。（2）随着问题规模）随着问题规模n的增大，两个算法的时间开销比为：的增大，两个算法的时间开销比为：亦随亦随之增大，之增大，（1）当输入量）当输入量n20时，有时，有说明当问题规模比较大的时候，说明当问题规模比较大的时候，A1比比A2有效的多。有效的多。第7页，本讲稿共36页问题问题3 3 算法的时间复杂度不仅仅依赖

8、于问题的规模，还算法的时间复杂度不仅仅依赖于问题的规模，还要与输入实例的初始状态有关（算法工作量）要与输入实例的初始状态有关（算法工作量）例例1-3 对于在数组对于在数组 中查找给定值中查找给定值k的算法，的算法，大致如下：大致如下：（1）i=n-1;(2)while(i0&(Ai!=k)(3)i-;(4)return i;语句（语句（3）的频度不仅与问题规模）的频度不仅与问题规模n有关，而且与输入实有关，而且与输入实例中例中A的各元素取值及的各元素取值及k的取值有关的取值有关第8页，本讲稿共36页(1)若若A中没有与中没有与k相等元素，则语句相等元素，则语句(3)的频度的频度f(n)=n;(

9、2)若若A中最后一个元素等于中最后一个元素等于k,则语句则语句(3)的频度的频度f(n)=0；第9页，本讲稿共36页问题问题4 最坏时间复杂度与平均时间复杂度最坏时间复杂度与平均时间复杂度最坏情况下的时间复杂度最坏情况下的时间复杂度是：算法在任何输入实例上的运是：算法在任何输入实例上的运行时间上的上界，保证了算法运行时间不会比任何更长；行时间上的上界，保证了算法运行时间不会比任何更长；平均情况下的时间复杂度平均情况下的时间复杂度是：所有可能的输入实例均以等概是：所有可能的输入实例均以等概率的出现的情况下，算法的期望运行时间。率的出现的情况下，算法的期望运行时间。时间复杂度和空间复杂度统称为算法

10、的复杂度。时间复杂度和空间复杂度统称为算法的复杂度。第10页，本讲稿共36页2 2 算法终止性证明算法终止性证明-良序原则良序原则n利用良序原则证明依赖于利用良序原则证明依赖于不可数集合不可数集合的命题的命题P(x)。n良序关系良序关系设设是集合是集合S上的一个良序关系，如果满足以下性质：上的一个良序关系，如果满足以下性质：（1）给定集合）给定集合S中元素中元素x,y,z，如果，如果xy，yz，则，则xz。（2）给定集合）给定集合S中元素中元素x,y，以下三种可能性恰有一种为真：，以下三种可能性恰有一种为真：xy，x=y，yx（3）如果）如果A是是S的任何非空子集，则的任何非空子集，则A中必有

11、一个元素中必有一个元素x，使得对于，使得对于A中所有的中所有的y，有，有xy。例如：自然数集合对于小于（例如：自然数集合对于小于（）关系良序。）关系良序。性质（性质（3 3）说明：任何一个非空的良序集合都有一）说明：任何一个非空的良序集合都有一个最小元素。（个最小元素。（实数集合实数集合？）？）？）？）第11页，本讲稿共36页良序原则良序原则命题命题1是集合是集合S的一个良序，当且仅当它满足性质（的一个良序，当且仅当它满足性质（1）和）和（2），并且对于所有的），并且对于所有的j1，不存在具有，不存在具有xj+1xj的无限的无限序列序列证明证明：（）设）设）设）设是集合是集合是集合是集合S S

12、的良序，如果存在这样的一个序列，的良序，如果存在这样的一个序列，的良序，如果存在这样的一个序列，的良序，如果存在这样的一个序列，则由该序列成员组成的集合则由该序列成员组成的集合则由该序列成员组成的集合则由该序列成员组成的集合A A是集合是集合是集合是集合S S的一个非空子集，的一个非空子集，的一个非空子集，的一个非空子集，A A不满足性质（不满足性质（不满足性质（不满足性质（3 3），与），与），与），与是集合是集合是集合是集合S S的良序矛盾。的良序矛盾。的良序矛盾。的良序矛盾。这样就可以在这样就可以在A中找到存在具有中找到存在具有xj+1xj的无限序列的无限序列。与给定条件矛盾，故假设错误

13、，。与给定条件矛盾，故假设错误，是集合是集合S的一个良序。证毕。的一个良序。证毕。（）若）若）若）若满足（满足（满足（满足（1 1），（），（），（），（2 2）但不满足（）但不满足（）但不满足（）但不满足（3 3）。设）。设）。设）。设A A是是是是S S一个没有最小元素的非空子集。由于一个没有最小元素的非空子集。由于一个没有最小元素的非空子集。由于一个没有最小元素的非空子集。由于A A非空，所以可非空，所以可非空，所以可非空，所以可以找到以找到以找到以找到,由于由于由于由于A A中无最小元素，故有中无最小元素，故有中无最小元素，故有中无最小元素，故有，由于，由于，由于，由于x x2 2也不

14、是最小元素，可以同样找到也不是最小元素，可以同样找到也不是最小元素，可以同样找到也不是最小元素，可以同样找到第12页，本讲稿共36页算法终止性证明算法终止性证明说明：说明：命题命题1可以用来证明算法的终止性：如果能够把一个计算的可以用来证明算法的终止性：如果能够把一个计算的各个状态映射到一个良序集各个状态映射到一个良序集S，使得计算的每一个步骤总是从，使得计算的每一个步骤总是从一个状态一个状态x进入到另一个状态进入到另一个状态y，并且有，并且有f(y)f(x)，则此算法必定，则此算法必定终止。终止。第13页，本讲稿共36页良序原则良序原则命题命题2设设是集合是集合S的一个良序，并且设的一个良序

15、，并且设p(x)是关于是关于S元素元素x的一个命题。的一个命题。如果如果p(x)能在能在p(y)对于所有的对于所有的yx为真的假定下得证，则为真的假定下得证，则p(x)对对S中中所有的所有的x为真为真。理论上说明算法终止性是可以证明的。理论上说明算法终止性是可以证明的。命题命题2是数学归纳法的推广，若是数学归纳法的推广，若S为自然数，则就是一般的简单的数为自然数，则就是一般的简单的数学归纳法。学归纳法。证明：命证明：命A是使得是使得p(x)为假的所有为假的所有x的集合。如果的集合。如果A非空，非空，A对于对于为良为良序，则序，则A含有一个最小元素含有一个最小元素x0，因此，因此p(y)对于所有

16、对于所有y x0为真。但这说为真。但这说明明p(x0)为真，所以为真，所以x0不在不在A中（因为中（因为A是使得是使得p(x)为假的所有为假的所有x的集合）的集合），与假设矛盾，因此，与假设矛盾，因此A必须为空，即必须为空，即p(x)总是为真。总是为真。第14页，本讲稿共36页Lattice 格格对任意一个偏序集来说对任意一个偏序集来说,其中每一对元素不一定都有其中每一对元素不一定都有最大下界或最小上界。最大下界或最小上界。设设是一个偏序集是一个偏序集,如果如果A中任意两个元素均有中任意两个元素均有最小上界和最大下界最小上界和最大下界,那么就说那么就说A关于偏序关于偏序“”作作成一个格成一个格

17、(Lattice),或直接称或直接称A为格。为格。第15页，本讲稿共36页递归算法递归算法递归算法，就是把一个输入规模较大的问题转化为一个输递归算法，就是把一个输入规模较大的问题转化为一个输入规模较小的同类问题，并反复进行这种转化，直到输入入规模较小的同类问题，并反复进行这种转化，直到输入规模小到可以直接求解为止。规模小到可以直接求解为止。递归算法的时间复杂度对应为相应的递归关系式递归算法的时间复杂度对应为相应的递归关系式如何求解？如何求解？第16页，本讲稿共36页3递归关系式的求解递归关系式的求解例：梵塔（汉诺（例：梵塔（汉诺（Hanoi）塔塔）问题）问题ABC递归关系：递归关系：h(n)=

18、2h(n-1)+1初始条件：初始条件：h(1)=1第17页，本讲稿共36页据说在东方的古国据说在东方的古国印度土地上，有一座印度土地上，有一座印度教印度教的神庙，这庙有一的神庙，这庙有一块黄铜板，板上插著三根细细的、镶上宝石的细针，细针像菜叶般粗，块黄铜板，板上插著三根细细的、镶上宝石的细针，细针像菜叶般粗，而高就像成人由手腕到肘关节的长。而高就像成人由手腕到肘关节的长。当印度教的主神当印度教的主神梵天梵天在创造地球这个世界时，就在其中的一根针上在创造地球这个世界时，就在其中的一根针上从下到上放了半径由大到小的六十四片圆金片环，这就是有名的梵塔从下到上放了半径由大到小的六十四片圆金片环，这就是

19、有名的梵塔或称或称汉内塔汉内塔（TowersofHanoi）。）。天神天神梵天梵天要这庙的僧侣，把这些金片全部由一根针移到另外一要这庙的僧侣，把这些金片全部由一根针移到另外一根指定的针上，一次只能移一片，不管在什么情况下，金片环的根指定的针上，一次只能移一片，不管在什么情况下，金片环的大小次序不能变更，小金片环永远只能放在大金片环上面。大小次序不能变更，小金片环永远只能放在大金片环上面。只要有一天这六十四片的金环能从指定的针上完全转移到另只要有一天这六十四片的金环能从指定的针上完全转移到另外指定的针上，世界末日就来到，芸芸众生、神庙一切都将消灭，外指定的针上，世界末日就来到，芸芸众生、神庙一切

20、都将消灭，万物尽入万物尽入极乐世界极乐世界去。去。第18页，本讲稿共36页递归关系的求解递归关系的求解-生成函数生成函数(母函数母函数)函数函数与序列与序列相对应，定义生成函数：对于序列相对应，定义生成函数：对于序列构造函数构造函数为序列为序列的生成函数，其中的生成函数，其中x是参数，只要是参数，只要序列序列an确定，则确定，则G只依赖于只依赖于x。反之，若。反之，若G已知，则序已知，则序列自然确定。列自然确定。第19页，本讲稿共36页生成函数与递归序列生成函数与递归序列寻找递归序列的通项寻找递归序列的通项1）构造递归序列的生成函数；）构造递归序列的生成函数；2）生成函数对于某些）生成函数对于

21、某些x值收敛，得到值收敛，得到g(x)的解的解析表达式；析表达式；3）将）将g(x)展开为幂级数，则展开为幂级数，则xn的系数就是递归序列的系数就是递归序列的通项的通项an的表达式。的表达式。第20页，本讲稿共36页生成函数生成函数对于河内塔问题，以对于河内塔问题，以h(n)为系数，构造其生成函数为系数，构造其生成函数H(x)，先求出先求出先求出先求出H(x)H(x)的解析表达式，然后展开为幂级数，其中的解析表达式，然后展开为幂级数，其中的解析表达式，然后展开为幂级数，其中的解析表达式，然后展开为幂级数，其中x xn n的系数即为要移动的次数。的系数即为要移动的次数。的系数即为要移动的次数。的

22、系数即为要移动的次数。第21页，本讲稿共36页生成函数生成函数得到第22页，本讲稿共36页生成函数生成函数得到 ，即为要求移动的次数。当当n=64时，要移动时，要移动264-1次，假设次，假设次，假设次，假设1s1s移动一次，需要移动一次，需要移动一次，需要移动一次，需要58495849亿年。亿年。第23页，本讲稿共36页2009年国际超级计算机超级计算机会议上，美国洛斯阿拉莫斯国家实验的IBMRoadrunner计算机被评选为世界上最快的超级计算机超级计算机速度达到了每秒速度达到了每秒1.105千万亿次千万亿次 计算速度计算速度空间换时间空间换时间第24页，本讲稿共36页“天河一号天河一号”

23、为我国首台千万亿次超级计算机为我国首台千万亿次超级计算机 每秒钟每秒钟1206万亿次万亿次的峰值速度和每秒的峰值速度和每秒563.1万万亿次的亿次的Linpack实测性能，使这台名为实测性能，使这台名为“天河一号天河一号”的计算机位居同日公布的中国的计算机位居同日公布的中国超级计算机前超级计算机前100强之首，也使中国成为强之首，也使中国成为继美国之后世界上第二个能够自主研制千继美国之后世界上第二个能够自主研制千万亿次超级计算机的国家。万亿次超级计算机的国家。这个速度意味着，如果用这个速度意味着，如果用“天河一天河一号号”计算一秒，则相当于全国计算一秒，则相当于全国13亿人连续计算亿人连续计算

24、88年。如果用年。如果用“天河一号天河一号”计算一天，一计算一天，一台当前主流微机得算台当前主流微机得算160年。年。“天河一号天河一号”的存储量，则相当于的存储量，则相当于4个国家图书馆藏书量个国家图书馆藏书量之和。之和。第25页，本讲稿共36页联想联想 曙光曙光 浪潮浪潮 联想深腾联想深腾7000系列系列百万亿次超级计算机系统百万亿次超级计算机系统2010年年6月月1日，中国首台实测性能超千万亿次的超级计算机日，中国首台实测性能超千万亿次的超级计算机曙光曙光“星云星云”高性能计算机系统高性能计算机系统于北京国家会议中心正式发布，超千万亿次的计算能力于北京国家会议中心正式发布，超千万亿次的计

25、算能力再次刷新了中国高性能计算的最高速度。在德国时间再次刷新了中国高性能计算的最高速度。在德国时间2010年年5月月31日公布的第日公布的第35届全球超级计算机届全球超级计算机TOP500排行榜中排名第二，创造了中国高性能计算机全球排名排行榜中排名第二，创造了中国高性能计算机全球排名的最好成绩。的最好成绩。浪潮浪潮“倚天倚天”的万亿次桌面超级计算机，售价的万亿次桌面超级计算机，售价5万元，开创出新的桌面超级万元，开创出新的桌面超级计算机细分市场。计算机细分市场。“倚天倚天”与普通台式机主机箱体积相仿，最高计算能力可达与普通台式机主机箱体积相仿，最高计算能力可达4万亿次万亿次/秒秒，相当于，相当

26、于40台服务器或台服务器或200台台PC的计算，而成本只有传统高性的计算，而成本只有传统高性能计算系统的能计算系统的1/5。更快的计算机还是更快的算法？更快的计算机还是更快的算法？第26页，本讲稿共36页递归关系的求解递归关系的求解-特征方程、特征根特征方程、特征根k阶常系数线性齐次递归关系阶常系数线性齐次递归关系：若若是常数，且是常数，且，则递归关系，则递归关系为为k阶常系数线性齐次递归关系阶常系数线性齐次递归关系其特征方程是其特征方程是 。Case1Case1：如果特征方程有如果特征方程有如果特征方程有如果特征方程有k k个互不相同的根个互不相同的根个互不相同的根个互不相同的根则通解为则通

27、解为则通解为则通解为其中其中其中其中只要求出特征方程的根，利用初始条件确定通解当中的待定系只要求出特征方程的根，利用初始条件确定通解当中的待定系只要求出特征方程的根，利用初始条件确定通解当中的待定系只要求出特征方程的根，利用初始条件确定通解当中的待定系数，可以得到数，可以得到数，可以得到数，可以得到原递归关系的解原递归关系的解原递归关系的解原递归关系的解。第27页，本讲稿共36页特征方程、特征根特征方程、特征根例例1解：对应的特征方程为解：对应的特征方程为特征方程的根为：特征方程的根为：特征方程的根为：特征方程的根为：通解为：通解为：通解为：通解为：由初始条件得到：由初始条件得到：由初始条件得

28、到：由初始条件得到：第28页，本讲稿共36页特征方程、特征根特征方程、特征根解得解得解得解得因此因此因此因此第29页，本讲稿共36页Case2：如果特征方程有如果特征方程有k个不同根个不同根其中其中，则通解形式为，则通解形式为第30页，本讲稿共36页特征方程、特征根特征方程、特征根例例2特征方程的根为：特征方程的根为：特征方程的根为：特征方程的根为：通解为：通解为：通解为：通解为：由初始条件得到由初始条件得到：解：对应的特征方程为解：对应的特征方程为解：对应的特征方程为解：对应的特征方程为第31页，本讲稿共36页特征方程、特征根特征方程、特征根解得解得因此因此第32页，本讲稿共36页递归关系的

29、求解递归关系的求解-递推递推例例3解：第33页，本讲稿共36页第一章作业第一章作业1 利用生成函数法求Fibonacci序列的通项序列的通项2 P21 1.1 1)3)6)9)1.2 2)5)第34页，本讲稿共36页3 计算如下C语言描述的嵌套循环中laugh+语句的执行次数：for(i=1;i=n;i*=2)for(j=1;j=i;j+)laugh+;第35页，本讲稿共36页实验实验1 1 多项式求值的算法设计、实现与复杂度分析多项式求值的算法设计、实现与复杂度分析要求要求：1 1）输入：输入一个多项式）输入：输入一个多项式 ，系数及，系数及x x的取值；的取值；2 2）输出：多项式的值，计算所需的加法和乘法次数；）输出：多项式的值，计算所需的加法和乘法次数；3 3）要求具有用户界面，通过用户界面输入及输出）要求具有用户界面，通过用户界面输入及输出4 4）语言）语言C+,JAVAC+,JAVA5 5）提交实验报告）提交实验报告+源程序（实验源程序（实验i+i+学号学号+姓名姓名）到）到 ise_ise_上机时间：上机时间：3 3，5 5，7 7，9 9，1111，1313，1515周二周二1-21-2节节 ，661661机房（暂定）机房（暂定）第36页，本讲稿共36页