算法分析与设计第一二三章1(算法与分析算法).ppt

1、2008-09-01,版权所有：杨波，武汉科技大学理学院,一个正六边形被分成了6个相同的小三角形,如果用红、黄两种颜色分别涂满小三角形，那么有（ ）种不同的涂法。（旋转后图案相同的认为是同一种涂法）,2008-09-01,版权所有：杨波，武汉科技大学理学院,第一章 数学预备知识 第二章 导引与基本数据结构第三章 递归算法,武汉科技大学理学院信息与计算科学系 杨 波 cookie_ 2008年9月,2008-09-01,版权所有：杨波，武汉科技大学理学院,序,专业基础课程： 数据结构、计算机语言 操作系统、编译 如何编写计算机程序： 数据结构+算法 = 程序 算法：计算机软件的“灵魂” 算法是计

2、算机科学和计算机应用的核心,2008-09-01,版权所有：杨波，武汉科技大学理学院,ACM国际大学生程序设计竞赛,ACM国际大学生程序设计竞赛（英文全称：ACM International Collegiate Programming Contest（ACM-ICPC或ICPC）是由美国计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。经过30多年的发展，ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。赛事目前由IBM公司赞助。,2008-09-01,版权所有：杨波，武汉科技大学理学院,内容,入门三本： 数

3、据结构与算法（傅清祥，王晓东编著） 程序设计导引及在线实践 作者: 李文新 ACM程序设计培训教程 吴昊 基础提高： 算法艺术与信息学竞赛 第二版 刘汝佳 算法设计与分析 王晓东 科曼：算法导论 组合数学 第三版 冯舜玺 译 计算几何算法设计与分析 周培德 Concrete Mathematics - A Foundation For Computer Science Ronald L. Graham ， Donald E. Knuth ， Oren Patashnik具体数学计算机程序设计艺术三卷 Knuth 组合数学的算法与程序设计 程序设计中的组合数学 吴文虎 图论的算法与程序设计,20

4、08-09-01,版权所有：杨波，武汉科技大学理学院,教材与参考书,教 材： 余祥宣等编著，计算机算法基础（第三版），华中理工大学出版社，2006年 参考书： 徐士良编，C常用算法程序集，华大学出版社，1998年 CLLIFORD A. SHAFFER著，A Practical Introduction to DATA STRUCTURES AND ALGORITHM ANALYSIS，电子工业出版社，1998年 卢开澄编，计算机算法导引，清华大学出版社，2003年,2008-09-01,版权所有：杨波，武汉科技大学理学院,1.1 算法,什么是算法？ 算法如数字、计算一样，是一个基本概念。 算

5、法是解一确定类问题的任意一种特殊的方法。 在计算机科学中，算法是使用计算机解一类问题的精确、有效方法的代名词。,算法是一组有穷的规则，它规定了解决某一特定类型问题的一系列运算。,2008-09-01,版权所有：杨波，武汉科技大学理学院,算法的五个重要特性,确定性、能行性、输入、输出、有穷性,1）确定性：算法的每种运算必须要有确切的定 义，不能有二义性。 例：不符合确定性的运算 5/0 将6或7与x相加 未赋值变量参与运算,2008-09-01,版权所有：杨波，武汉科技大学理学院,2）能行性 算法中有待实现的运算都是基本的运算，原理上每种运算都能由人用纸和笔在“有限”的时间内完成。 例：整数的算

6、术运算是“能行”的 实数的算术运算是“不能行”的,2008-09-01,版权所有：杨波，武汉科技大学理学院,3）输入 每个算法有0个或多个输入。这些输入是在算法开始之前给出的量，取自于特定的对象集合定义域（或值域）,4）输出 一个算法产生一个或多个输出，这些输出是同输入有某种特定关系的量。,2008-09-01,版权所有：杨波，武汉科技大学理学院,5）有穷性 一个算法总是在执行了有穷步的运算之后终止。 计算过程：只满足确定性、能行性、输入、输出四个特性的一组规则。 算法和计算过程的区别： 计算过程：操作系统(不终止的运行过程) 算法是“可以终止的计算过程” 算法的时效性：只能把在相当有穷步内终

7、止的算法投入到计算机上运行,2008-09-01,版权所有：杨波，武汉科技大学理学院,算法学习的内容,如何设计算法：设计策略，创造性的活动 如何表示算法 条列式的步骤 流程图 伪码 程序语言 如何确认算法：证明算法的正确性 如何分析算法：时间和空间需求的定量分析 如何测试算法 调试：“调试只能指出有错误，而不能指出它们不存在错误” 作时空分布图：验证分析结论，优化算法设计,2008-09-01,版权所有：杨波，武汉科技大学理学院,算法学习的内容,如何设计算法：设计策略，创造性的活动 如何表示算法 条列式的步骤 流程图 伪码 程序语言 如何确认算法：证明算法的正确性 如何分析算法：时间和空间需求

8、的定量分析 如何测试算法 调试：“调试只能指出有错误，而不能指出它们不存在错误” 作时空分布图：验证分析结论，优化算法设计,2008-09-01,版权所有：杨波，武汉科技大学理学院,算法学习的内容,如何设计算法：设计策略，创造性的活动 如何表示算法 条列式的步骤 流程图 伪码 程序语言 如何确认算法：证明算法的正确性 如何分析算法：时间和空间需求的定量分析 如何测试算法 调试：“调试只能指出有错误，而不能指出它们不存在错误” 作时空分布图：验证分析结论，优化算法设计,2008-09-01,版权所有：杨波，武汉科技大学理学院,1.2 分析算法,算法分析 对算法所消耗的资源（时间和空间）进行估算

9、算法分析的目的 预计所涉及的算法能在什么样的环境中有效地运行，在最好、最坏和平均情况下执行得怎么样。 对同一问题的不同算法进行时空耗费两方面的分析 算法分析的意义 通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。 算法分析是计算机领域的“古老”而“前沿”的课题。,2008-09-01,版权所有：杨波，武汉科技大学理学院,重要假设,计算机模型的假设 计算机形式理论模型： Turing机模型 通用计算机模型： 顺序计算机 有足够的“内存” 能在固定的时间内存取数据单元,2008-09-01,版权所有：杨

10、波，武汉科技大学理学院,计算约定,算法的执行时间= 其中，fi是算法中用到的某种运算i的次数称为该运算的“频率计数”。 ti是该运算执行一次所用的时间 与程序语言和硬件有关。,2008-09-01,版权所有：杨波，武汉科技大学理学院,时间囿界于常数的运算： 基本算术运算，如整数、浮点数的加、减、乘、除 字符运算、赋值运算、过程调用等 特点：尽管每种运算的执行时间不同，但一般只花一 个固定量的时间（单位时间）就可完成。 其他运算： 字符串操作：与字符串中字符的数量成正比 记录操作：与记录的属性数、属性类型等有关 特点：运算时间无定量。,2008-09-01,版权所有：杨波，武汉科技大学理学院,工

11、作数据集的选择,编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。 编制测试数据是程序测试与算法分析中的关键技术之一。 作为算法分析的数据集：反映算法的典型特征 作为程序正确性及性能测试的数据集：测试程序的对错，反映对性能指标产生影响的方面，如边界值,2008-09-01,版权所有：杨波，武汉科技大学理学院,算法分析的两阶段,事前分析： 求算法的一个时间/空间限界函数，即通过对算法的“理论”分析，得出关于算法时间和空间特性的特征函数与计算机物理软硬件没有直接关系。 事后测试： 将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用

12、等统计资料，进行分析判断直接与物理实现有关。,2008-09-01,版权所有：杨波，武汉科技大学理学院,目的：试图得出关于算法特性的一种形式描述，以“理论上”衡量算法的“好坏”。 如何给出反映算法特性的描述？ 统计算法中各种运算的执行情况，包括： 引用了哪些运算 每种运算被执行的次数（频率计数） 该种运算执行一次所花费的时间等。 算法的执行时间=,事前分析,2008-09-01,版权所有：杨波，武汉科技大学理学院,频率计数,频率计数：算法中语句或运算的执行次数。 例： x=x+y; for(i=1;i=n;i+) for(i=1;i=n;i+) x=x + y ; for(j=1;j=n;j+

13、) x=x +y; (a) (b) (c) 分析： (a)： x=x+y执行了1次 (b)： x=x+y执行了n次 (c)： x=x+y执行了n2次,2008-09-01,版权所有：杨波，武汉科技大学理学院,在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。,2008-09-01,版权所有：杨波，武汉科技大学理学院,语句的数量级：执行它的频数 算法的数量级：所有语句执行频数的和 算法的计算时间：（实际算法分析中）看成问题规模n的函数，记作T(n)。 n可以是输入量，输出量，或两者之和。 n可以是某种测度（数组的维数，图的边数等）,2008-09-0

14、1,版权所有：杨波，武汉科技大学理学院,例 1 下面是查找一维n元数组中最大元素的算法。该算法一次遍历数组中的每个元素，并保存当前的最大元素，被称为“最大元素顺序检索”。 Public static int largest(int array,int n) int currlarge=0; for(int i=0;icurrlarge) currlarge=arrayi; return currlarge; ,2008-09-01,版权所有：杨波，武汉科技大学理学院,分析方法：找近似时间 问题规模n（数组的维数） 基本运算，将存放的当前最大数与数组每个元素比较 假定每次比较的时间为c 变量i增

15、加所需时间 找到一个新的最大元素时要做的工作 不考虑c的实际值，不考虑初始化时所需的一小部分时间，只想得到该算法的一个合理近似时间。 计算时间T(n)=cn 增长率：当问题规模增大时，算法代价增长的速度。 线性增长率,2008-09-01,版权所有：杨波，武汉科技大学理学院,例 2 一个整数数组的第一个元素值复制给另一个变量。 分析： 问题规模n 基本运算是赋值 T(n)=c1 （c1表示赋值所需时间），与问题规模无关。 常数运行时间,2008-09-01,版权所有：杨波，武汉科技大学理学院,例 3 程序段如下： sum=0; for(i=1;i=n;i+) for(j=1;j=n;j+) s

16、um+; 分析： 问题规模n 基本运算是累加，时间c2 （忽略初始化，循环变量的累加） T(n)=c2 n2 二次增长率,2008-09-01,版权所有：杨波，武汉科技大学理学院,T(n)的形式： 多项式增长率 T(n)=c T(n)=cn T(n)=cn2 指数增长率 T(n)=2n 对数增长率 T(n)=logn,2008-09-01,版权所有：杨波，武汉科技大学理学院,最佳、最差和平均情况,例 从一个n元数组中找出一个给定的K（假定数组中有且仅有一个元素值为K）。顺序检索法将从第一个元素开始，一次检索每一个元素，直到找到K为止，算法完成。 最佳情况：检索1个元素 最差情况：检索n个元素

17、平均情况：检索n/2个元素 算法分析时： 最佳情况一般不做研究。发生概率小，对于条件的考虑太乐观，不能作为算法性能的代表。 最差情况有必要。能知道算法至少能执行得多快，在实时系统中很重要 平均情况。算法的“典型”表现，适用于对许多不同的输入运行多次。但平均情况分析需考虑数据的分布情况。,2008-09-01,版权所有：杨波，武汉科技大学理学院,换一台更快的计算机，还是换一种更快的算法？,规定时间内，速度是原来十倍的计算机所处理问题规模增长情况。假设原来的计算机能在一小时内完成10,000个基本操作。,2008-09-01,版权所有：杨波，武汉科技大学理学院,渐近分析,渐近分析是指当输入规模很大

18、，或者说达到极限（微积分意义上）时，对一种算法的研究。 计算时间或其他开销时，忽略系数。 注意力集中在重要的一点：增长率。 用于解决问题规模很大时的算法分析。 是对算法资源开销的一种不精确的估算方法，它提供了对算法资源开销进行评估的简单化的模型。,2008-09-01,版权所有：杨波，武汉科技大学理学院,上限,定义1：如果存在两个正常数c和n0，对于所有的nn0，有 |T(n)|c|g(n)| 则记作T(n)=O(g(n) 说明： T(n)表示算法的实际运行时间 g(n)是上限的一个函数表达式 常数n0是使上限成立的n的最小值 必须能找到一个常数c ，而c确切是多少无关紧要 需考虑算法在最好，

19、最坏和平均情况下的三种上限 含义： 如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间T(n)的一个上界函数。 T(n)的数量级就是g(n)。 试图求出最小的g(n)（“最紧”的上限），使得T(n)=O(g(n) 。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例：考虑数组中某个特定元素的检索法。若访问并检查数组中的一个元素需要时间cs（cs为正数），那么在平均情况下T(n)=csn/2。 存在n0=1，存在c=cs，对于所有nn0， 有|T(n)|=|csn/2|cs|n|=c|n|。 所以T(n)=O(n),2

20、008-09-01,版权所有：杨波，武汉科技大学理学院,多项式定理,定理： 若A(n)=amnm+a1n+a0是一个m次多项式，则有 A(n)=O(nm) 即：变量n的固定阶数为m的任一多项式，与此多项式的最高阶 nm同阶。 证明：取n0=1,当nn0时，有 |A(n)|am|nm+|a1|n+|a0| (|am|+|am-1|/n+|a0|/nm) nm (|am|+|am-1|+|a0|) nm 令c= |am|+|am-1|+|a0| 则，定理得证。 计算时间为m阶的多项式的算法，其时间都可用O(nm)来表示,2008-09-01,版权所有：杨波，武汉科技大学理学院,算法按时间的分类,多

21、项式时间算法：可用多项式（函数）对其计算时间限界 的算法。 常见的多项式限界函数有： O(1) O(logn)O (n)O(nlogn)O(n2)O (n3) 指数时间算法：计算时间用指数函数限界的算法 常见的指数时间限界函数： O(2n) O(n！)O(nn) 说明：当n取值较大时，指数时间算法和多项式时间算法在计算时 间上非常悬殊。,2008-09-01,版权所有：杨波，武汉科技大学理学院,典型的计算时间函数曲线,2008-09-01,版权所有：杨波，武汉科技大学理学院,下限,定义2 如果存在两个正常数c和n0，对于所有的nn0， 有 |T(n)|c|g(n)| 则记作T(n) =(g(n

22、) 含义： 如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是不小于|g(n)|的一个常数倍。所以g(n)是计算时间T(n)的一个下界函数。 试图求出“最大”的g(n)（“最紧”的下限），使得T(n)=(g(n)。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例：在n维数组中寻找值为k的元素的顺序检索法。在平均情况和最差情况下，算法在(n)中，因为在这两种情况下，都至少要检索cn个元素（在平均情况下c=1/2,在最差情况下c=1）。,2008-09-01,版权所有：杨波，武汉科技大学理学院,下限,定义2*：若存在正常数c，有无穷多个n使|T(n)|c|g(n)|成立

23、，则称T(n)=(n)。 此定义只要求|T(n)|c|g(n)|发生得足够频繁,2008-09-01,版权所有：杨波，武汉科技大学理学院,例：假定某个算法的运行时间函数如下：,分析： n0且n为偶数时，|n2/100|(1/100)|n2| 。取c=1/100，则有无数多个n（偶数的n）使|T(n)|c|n2|成立。所以T(n)=(n2) 。,2008-09-01,版权所有：杨波，武汉科技大学理学院,表示法,定义3 如果存在正常数c1，c2和n0，对于所有的nn0，有 c1|g(n)|f(n)|c2|g(n)| 则记作f(n)=(g(n) 含义： 既有f(n)=(g(n)，又有f(n)=O(g

24、(n) 例：平均情况下，顺序检索既为O(n)又为(n)，所以说平均情况下是(n)。,2008-09-01,版权所有：杨波，武汉科技大学理学院,渐近分析化简4法则,若f(n)=O(g(n) ，且g(n)=O(h(n)，则f(n)=O(h(n)； 若f(n)=O(kg(n)，对于任意常数k0成立，则f(n)=O(g(n)； 若f1(n) =O(g1(n)，f2(n) =O(g2(n)，则f1(n)+f2(n)=O(max(g1(n), g2(n)； 若f1(n) =O(g1(n)，f2(n) =O(g2(n)，则f1(n)f2(n)=O(g1(n)g2(n)。,法则1说明：如果g(n)是算法代价函

25、数的一个上限，则g(n)的任意上限h(n)也是该算法代价的上限。对于表示法有类似的性质：若如果g(n)是算法代价函数的一个下限，则g(n)的任意下限h(n)也是该算法代价的下限。表示法同理。,法则2的意义在于使我们能够忽略O表示法中的常数因子。对于和表示法同样有这样的性质。,法则3说明，顺序给出一个程序的两个部分（两组语句或两段代码），我们只需要考虑其中开销大的部分。类似地，在和表示法中，也只看开销大的部分就可以了。,法则4用于分析程序中的简单循环。如果要有限次地重复某种操作，且每次重复的开销相等，则总开销为每次的开销与重复次数之积。对于和表示法结论也成立。,2008-09-01,版权所有：杨

26、波，武汉科技大学理学院,可以在计算任何算法开销的近似增长率时，忽略所有的常数和低次项。,2008-09-01,版权所有：杨波，武汉科技大学理学院,程序运行时间的计算,例1：首先看一个给整型变量赋值的简单语句： a=b； 分析：该语句执行时间为一个常量，为(1)。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例2：简单的循环： sum=0; for(i=1;i=n;i+) sum+=n; 分析： 第一个语句时间代价为(1) for循环重复了n次 第三个语句时间代价为一常量 由法则4，后两行的for循环总时间代价为(n) 根据法则3，整个程序段时间代价为(n)。,2008-09-01

27、,版权所有：杨波，武汉科技大学理学院,例3：下面是一个含有多个for循环的程序段，其中有些是嵌套的。 sum=0; for(j=1;jn;j+) for(i=1;i=j;i+) sum+; for(k=1;k=n;k+) Ak=k-1; 分析： 该程序段有三个相对独立的片断：一个赋值语句和两个for循环结构。 赋值语句时间代价为常量，记作c1 ； 第二个for循环时间代价为c2n=(n)； 第一个for循环时间代价为 ，即(n2) ； 根据法则3，总运行时间为(c1+c2n+c3n2)，可化简为(n2)。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例4：比较下面两段程序的算法分

28、析： sum1=0; for(i=1;i=n;i+) for(j=1;j=n;j+) sum1+; sum2=0; for(i=1;i=n;i+) for(j=1;j=i;j+) sum2+; 分析： 此两个程序段的时间代价都为(n2)，不过第二个程序段运行时间约为第一个的一半。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例5：并非所有的嵌套for循环时间代价都是(n2)。 sum1=0; for(k=1;k=n;k*=2) for(j=1;j=n;j+) sum1+; sum2=0; for(k=1;k=n;k*=2) for(j=1;j=k;j+) sum2+;,分析： 第

29、一段程序 外层for循环执行了2x=n，x=logn次 内层循环执行次数恒为n 。 总时间代价为 第二段程序 外层循环也执行了logn次 内层循环重复k次 总和表示为,2008-09-01,版权所有：杨波，武汉科技大学理学院,常用整数求和公式,在分析算法中，经常会遇到以下形式的表达式：,常见如下：,(1),(2),(3),2008-09-01,版权所有：杨波，武汉科技大学理学院,常用整数求和公式,(4),(4)的特例有：,(5),(6),(6)的特例有：,(7),2008-09-01,版权所有：杨波，武汉科技大学理学院,常用整数求和公式,(7),(7)的推论有：,(8),(2)的推广有：,(7

30、),2008-09-01,版权所有：杨波，武汉科技大学理学院,对数公式：,(1),(2),(3),(4),(5),2008-09-01,版权所有：杨波，武汉科技大学理学院,数学工具,递推关系求解 公式法 差分方程法 生成函数（母函数）,2008-09-01,版权所有：杨波，武汉科技大学理学院,递推关系求解,例1 某算法（Hanoi塔问题）的递归时间复杂性由下面递归方程给出，试作渐近分析。,此算法的时间复杂性为：,2008-09-01,版权所有：杨波，武汉科技大学理学院,例2 某问题（分治法）的算法时间耗费由下面递归方程给出，试作渐近分析。,2008-09-01,版权所有：杨波，武汉科技大学理学

31、院,公式法,例1 考虑,分析：a=9，b=3，c=1，ab,例2 考虑,分析：a=1，b=3/2，c=1，d(n)=c,2008-09-01,版权所有：杨波，武汉科技大学理学院,差分方程法,对于某些递归方程，一般项并不是由一个低次项而是由多个低次项表示的。如： (1) T(n)=a1T(n-1)+a2T(n-2)+akT(n-k)， nk，ai，i=1,k为常数，ak0。,K阶常系数齐次差分方程： T(n)-a1T(n-1)-a2T(n-2)-akT(n-k)=0,K阶常系数齐次差分方程的特征方程： xk-a1xk-1-a2xk-2-ak-1x-ak=0,2008-09-01,版权所有：杨波，

32、武汉科技大学理学院,1) 如果k个根互不相同，则齐次方程的通解为：,其中ci，i=1,k为待定常数，由初始条件确定,2) 如果有r个重根，qi=qi+1=qi+r-1则通解为：,2008-09-01,版权所有：杨波，武汉科技大学理学院,例：求解递归方程,2008-09-01,版权所有：杨波，武汉科技大学理学院,例：求解递归方程,2008-09-01,版权所有：杨波，武汉科技大学理学院,差分方程法,(2) T(n)=a1T(n-1)+a2T(n-2)+akT(n-k)+f(n)， nk，ai，i=1,k为常数，ak0 ，f(n)0 。,K阶常系数非齐次差分方程： T(n)-a1T(n-1)-a2

33、T(n-2)-akT(n-k)=f(n),通解是：,对应齐次方程的通解,特解,2008-09-01,版权所有：杨波，武汉科技大学理学院,特解求法 试探法（因为并不存在寻找特解的一般方法） 根据f(n)的特点推测特解形式，用代定系数法确定系数。 利用叠加原理将f(n)线性分解成若干个单项之和，并求出各单项的特解，然后叠加得到f(n)的特解。这使得试探法更有效,2008-09-01,版权所有：杨波，武汉科技大学理学院,三种特殊形式的f(n)，其中pi, i=0,1,s为待定的常数，c(x)为特征多项式。,2008-09-01,版权所有：杨波，武汉科技大学理学院,例1 求递归方程：T(n)+5T(n-1)+6T(n-2)=3n2的一个特解。 解： c(x)=x2+5x+6=0 x1=-2 x2=-3 c(1)0 设T*(n)=p1n2+p2n+p3 得p1=1/4 p2=17/24 p3=115/288,2008-09-01,版权所有：杨波，武汉科技大学理学院,例2 求解递归方程：