算法设计与分析第1章.ppt

算法设计与分析,湖南人文科技学院计算机系 授课：肖敏雷 邮箱：minlei_,关于本课程,课程目的：计算机算法设计与分析导引 不是一门试验或程序设计课程 也不是一门数学课程 教材：计算机算法设计与分析-王晓东 前导课：数据结构+程序设计 参考资料： 算法设计与分析C+语言描述 陈慧南编 电子工业出版社 计算机算法基础(第三版) 余祥宣 华中科技大学,本课程的主要任务 算法学习将涉及5个方面的内容： 1）设计算法：创造性的活动 2）表示算法：思想的表示形式 3）确认算法：证明算法的正确性 程序的证明 4）分析算法：算法时空特性分析 5）测试程序：调试和作出时空分布图 本课程集中于学习算法的设计与分析。通过学习，掌握计算机算法设计和分析基本策略与方法，为设计更复杂、更有效的算法奠定基础,第1章 算法概述,学习要点: 理解算法的概念。 理解什么是程序，程序与算法的区别和内在联系。 掌握算法的计算复杂性概念。 掌握算法渐近复杂性的数学表述。 掌握用C+语言描述算法的方法。,算法的研究内容,问题是否可解 1930s 研究集中于判断特定问题在计算机上是否可解，基本方法为：选定一个计算模型，观察是否能在该模型上创建能解决问题的算法。这些计算模型包括：Post machines、Turing machines等。这一阶段的成果是：大部分问题为不可解。 高效率的解决方法 随着计算机的发展和数据资源的增加，算法研究转向针对可解的问题，找到高效率的解决方法。,算法的五个重要特性（其他教材的描述） 确定性、能行性、输入、输出、有穷性,1）确定性：算法的每种运算必须要有确切的定义，不能有二义性。 例：不符合确定性的运算 5/0 将6或7与x相加,2）能行性（教材中没有） 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在有限的时间内完成；它们可以通过已经实现的基本运算执行有限次来实现。 例：整数的算术运算是“能行”的 实数的算术运算是“不能行”的，某些实数只能由无限长的十进制数表示，像这样的2个数相加就违背了能行性这一特性。,3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合定义域（或值域）,4）输出 一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。,5）有穷性 一个算法总是在执行了有穷步的运算之后终止。,程序(Program),程序是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)（有限性）。 例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。 操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。,问题求解(Problem Solving),理解问题,精确解或近似解 选择数据结构 算法设计策略,设计算法,算法复杂性分析,算法复杂性 = 算法所需要的计算机资源 算法的时间复杂性T(n)； 算法的空间复杂性S(n)。 其中n是问题的规模（输入大小）。,算法的时间复杂性,（1）最坏情况下的时间复杂性 Tmax(n) = max T(I) | size(I)=n （2）最好情况下的时间复杂性 Tmin(n) = min T(I) | size(I)=n （3）平均情况下的时间复杂性 Tavg(n) = 其中I是问题的规模为n的实例，p(I)是实例I出现的概率。,对于：T(n) , as n ; 如果存在：(T(n) - t(n) )/ T(n) 0 ，as n; 就称：t(n)是T(n)的渐近性态，为算法的渐近复杂性。 在数学上， t(n)是T(n)的渐近表达式，是T(n)略去低阶项留下的主项。它比T(n) 简单。 比如：当 T(n) n2+4nlogn+7时， t(n)的一个答案是n2,介绍几个渐近分析的记号,大O记号 (上界) 记号 (下界) 记号 (同阶) 小o记号 （低阶）,1 大O记号,定义1 设函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数c和n0，使得当nn0时，有f(n)cg(n)，则记做f(n) = O(g(n)，称为大O记号（big Oh notation）。 一个算法具有O(g(n)的运行时间，是指当n足够大时，算法的运行时间不超过g(n）的常数倍， g(n)是它的一个上界。,例1 f(n) = 2n + 3 = O(n) 当n3时，2n+33n，所以，可选c = 3，n0 = 3。对于nn0，f(n) = 2n + 33n，所以，f(n) = O(n)，即2n + 3O(n)。这意味着，当n3时，例1的程序步不会超过3n，2n + 3 = O(n)。,例2 f(n) = 10n2 + 4n + 2 = O(n2) 对于n2时，有10n2 + 4n + 210n2 + 5n，并且当n5时，5nn2，因此，可选c = 11, n0 = 5；对于nn0，f(n) = 10n2 + 4n + 211n2，所以f(n) = O(n2)。,例3 f(n) = n！= O(nn) 对于n1，有n(n 1)(n 2) 1nn，因此，可选c = 1，n0 = 1。对于nn0，f(n) = n！nn，所以，f(n) = O(nn)。,定理1 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多项式，且am0，则f(n) = O(nm)。 证明：取n0 = 1，当nn0时，有 f(n)= amnm + am1nm1 + + a1n + a0 |am|nm + |am1|nm1 + + |a1|n + |a0| (|am| + |am1|/n + + |a1|/nm1 + |a0|/nm) nm (|am| + |am1| + + |a1| + |a0|) nm 可取c= |am| + |am1| + + |a1| + |a0|，定理得证。,渐近时间复杂度 使用大O记号及下面定义的几种渐近表示法表示的算法时间复杂度，称为算法的渐近时间复杂度（asymptotic complexity）。 只要适当选择关键操作，算法的渐近时间复杂度可以由关键操作的执行次数之和来计算。一般地，关键操作的执行次数与问题的规模有关，是n的函数。 关键操作通常是位于算法最内层循环的语句。,【程序1】 矩阵乘法 for（i=0; in; i+） /比较运算n+1次 for（j=0; jn; j+） /比较运算n(n+1)次 cij=0; /n2 for（k=0; kn; k+） /比较运算n2(n+1) cij+=aik*bkj; /n3 程序中所有语句执行次数为：(n)=2n3+3n2+2n+1 渐进时间复杂度为：O(n3)； 如果将cij+=aik*bkj; 看成关键操作，它的执行次数n3，同样也可以得到O(n3)。,2 记号,定义2 设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在两个正常数 c和n0，使得当nn0时，有f(n)cg(n)，则记做f(n)= (g(n)，称为记号（omega notation）。 用于表示一个算法运行时间的下界。称一个算法具有(g(n)的运行时间，是指当n足够大时，该算法至少需要g(n)的常数倍的时间量。,例1 f(n) = 2n + 3 = (n) 对所有n，2n+32n，可选c = 2，n0=0。对于nn0，f(n) = 2n+32n，所以，f(n) = (n)，即2n + 3(n)。,f(n) = 2n + 3 = O(n) 当n3时，2n+33n，所以，可选c = 3，n0 = 3。对于nn0，f(n) = 2n + 33n，所以，f(n) = O(n)，即2n + 3O(n)。这意味着，当n3时，例1的程序步不会超过3n，2n + 3 = O(n)。,例2 f(n) = 10n2 + 4n + 2 = (n2) 对所有n，10n2 + 4n + 210n2，可选c = 10，n0 = 0。对于nn0，f(n) = 10n2 + 4n + 210n2，所以，f(n) = (n2)。,f(n) = 10n2 + 4n + 2 = O(n2) 对于n2时，有10n2 + 4n + 210n2 + 5n，并且当n5时，5nn2，因此，可选c = 11, n0 = 5；对于nn0，f(n) = 10n2 + 4n + 211n2，所以f(n) = O(n2)。,定理2 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多项式，且am0，则f(n) = (nm)。 证明：略。,3 记号,定义3 设有函数f(n)和g(n)是定义在非负整数集合上的正函数，如果存在正常数c1，c2和n0，使得当nn0时，有c1 g(n)f(n)c2 g(n)，则记做f(n) = (g(n)，称为记号（Theta notation）。 用于表示算法运行时间具有与g(n)相同的阶。称一个算法具有(g(n)的运行时间，是指当n足够大时，该算法的运行时间大约为g(n)的常数倍的时间量。,例1 f(n) = 2n + 3 = (n)，即2n + 3(n)。 例2 f(n) = 10n2 + 4n + 2 = (n2)。 定理3 如果f(n) = amnm + am1nm1 + + a1n + a0是m次多项式，且am0，则f(n) = (nm)。,4 小o记号,定义4 f(n) = o(g(n)当且仅当f(n) = O(g(n)且f(n) (g(n) 用于表示算法运行时间f(n) 的阶比g(n)低。 例1 f(n)=2n+3=o(n2)，即2n+3o(n2)。,计算时间的数量级对算法有效性的影响 数量级的大小对算法的有效性有决定性的影响。 例：假设解决同一个问题的两个算法，它们都有n个输入，计算时间的数量级分别是n2和nlogn。则， n=1024：分别需要1048576和10240次运算。 n=2048：分别需要4194304和22528次运算。 分析：在n加倍的情况下，一个(n2)的算法计算时间增长4 倍，而一个(nlogn)算法则只用两倍多一点的时间即 可完成。,多项式时间算法：可用多项式（函数）对其计算时间限界的算法。 常见的多项式限界函数有： (1) (logn) (n) (nlogn) (n2) (n3) 指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数： (2n) (n！) (nn) 说明：当n取值较大时，指数时间算法和多项式时间 算法在计算时间上非常悬殊。,算法分类（计算时间）,典型的计算时间函数曲线,当数据集的规模很大时，要在现有的计算机系统上运行具有比(nlogn)复杂度还高的算法是比较困难的。 指数时间算法只有在n取值非常小时才实用。 要想在顺序处理机上扩大所处理问题的规模，有效的途径是降低算法的计算复杂度，而不是（仅仅依靠）提高计算机的速度。,计算时间函数值比较,一个问题可以设计不同的算法来求解，针对同一个问题的算法也许基于完全不同的思路。 求两个整数的最大公约数可以采用欧几里德算法，也可以采用连续整数检测算法，两种算法的解题速度会有明显的差异。 同一个算法也可以采用不同的形式来表示。例如，欧几里德算法可以写成递归形式，也可以写成迭代形式。,欧几里德算法(辗转相除法) 计算两个整数m和n（0mn)的最大公约数，记为gcd(m, n)。 辗转相除法：若m=0，则n和m的最大公约数等于n；若m0，则n和m的最大公约数等于m和用n除m的余数的最大公约数。 注：辗转相除法是由古希腊欧几里德（约公元前330-275年）在他的几何原本中提出的。,【程序1】 欧几里德递归算法 void Swap(int ,【程序2】 欧几里德迭代算法 int Gcd(int m,int n) if (m=0)return n; if (n=0)return m; if (mn) Swap(m,n); while(m0) int c=n%m;n=m;m=c; return n; ,【程序3】 Gcd的连续整数检测算法 int Gcd(int m,int n) if (m=0)return n; if (n=0)return m; int t=mn?n:m; while (m%t | n%t) t-; return t; ,作业: P5 算法分析题:1、2、3、4、5 P6 算法实现题：1,汉诺塔问题（tower of Hanoi） 假定有三个塔座：X，Y，Z，在塔座X上有n个直径大小各不相同，按圆盘大小从小到大编号为1，2，n的圆盘。现要求将X塔座上n个圆盘移到塔座Y上，并仍按同样顺序叠排。 圆盘移动时必须遵循下列规则： （1）每次只能移动一个圆盘； （2）圆盘可以加到塔座X，Y，Z中任意一个上； （3）任何时刻都不能将一个较大的圆盘放在较小的圆盘之上。,第一次实验 C/C+环境及递归算法,汉诺塔问题 void Move(char x, char y) /将第n个圆盘从塔座x移到塔座y的顶部 cout “ y endl; ,void Hanoi(int n, char x, char y, char z) /将x上的n个圆盘移到y上顺序不变，借助于z if (n0) Hanoi(n-1, x, z, y); /将x上的n-1个圆盘移到z上顺序不变，借助于y Move(x,y); Hanoi(n-1, z, y, x); /将z上的n-1个圆盘移到y上顺序不变，借助于z ,排列问题 设计一个递归算法生成n个元素r1,r2,rn的全排列。 设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示