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

《算法分析与设计第一二三章1(算法与分析算法).ppt》由会员分享，可在线阅读，更多相关《算法分析与设计第一二三章1(算法与分析算法).ppt（76页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

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

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

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

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

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

9、分析n如何测试算法如何测试算法 调试：“调试只能指出有错误，而不能指出它们不存在错误”作时空分布图：验证分析结论，优化算法设计2008-09-01版权所有：杨波，武汉科技大学理学院 1.2 分析算法分析算法n算法分析 对算法所消耗的资源（时间和空间）进行估算n算法分析的目的q预计所涉及的算法能在什么样的环境中有效地运行，在最好、最坏和平均情况下执行得怎么样。q对同一问题的不同算法进行时空耗费两方面的分析n算法分析的意义 通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。算法分析是计算机领域的“古老”而

10、“前沿”的课题。2008-09-01版权所有：杨波，武汉科技大学理学院 重要假设重要假设计算机模型的假设n计算机形式理论模型：Turing机模型n通用计算机模型：q顺序计算机q有足够的“内存”q能在固定的时间内存取数据单元2008-09-01版权所有：杨波，武汉科技大学理学院 计算约定计算约定算法的执行时间=其中，fi是算法中用到的某种运算i的次数称为该运算的“频率计数”。ti是该运算执行一次所用的时间 与程序语言和硬件有关。2008-09-01版权所有：杨波，武汉科技大学理学院 n时间囿界于常数的运算：q基本算术运算，如整数、浮点数的加、减、乘、除q字符运算、赋值运算、过程调用等 特点：尽管

11、每种运算的执行时间不同，但一般只花一 个固定量的时间（单位时间）就可完成。n其他运算：q字符串操作：与字符串中字符的数量成正比q记录操作：与记录的属性数、属性类型等有关 特点：运算时间无定量。2008-09-01版权所有：杨波，武汉科技大学理学院 工作数据集的选择工作数据集的选择n编制能够反映算法在最好、平均、最坏情况下工作的数据配置。然后使用这些数据配置运行算法，以了解算法的性能。编制测试数据是程序测试与算法分析中的关键技术之一。q作为算法分析的数据集：反映算法的典型特征q作为程序正确性及性能测试的数据集：测试程序的对错，反映对性能指标产生影响的方面，如边界值2008-09-01版权所有：杨

12、波，武汉科技大学理学院 算法分析的两阶段算法分析的两阶段n事前分析：求算法的一个时间/空间限界函数，即通过对算法的“理论”分析，得出关于算法时间和空间特性的特征函数与计算机物理软硬件没有直接关系。n事后测试：将算法编制成程序后实际放到计算机上运行，收集其执行时间和空间占用等统计资料，进行分析判断直接与物理实现有关。2008-09-01版权所有：杨波，武汉科技大学理学院 n目的：试图得出关于算法特性的一种形式描述，以“理论上”衡量算法的“好坏”。n如何给出反映算法特性的描述？统计算法中各种运算的执行情况，包括：q引用了哪些运算q每种运算被执行的次数（频率计数）q该种运算执行一次所花费的时间等。算

13、法的执行时间=事前分析事前分析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+)x=x+y;(a)(b)(c)分析：(a)：x=x+y执行了1次(b)：x=x+y执行了n次(c)：x=x+y执行了n2次 2008-09-01版权所有：杨波，武汉科技大学理学院 n在事前分析中，只限于确定与所使用的机器及其他环境因素无关的频率计数，依此建立一种理论上分析模型。2008-09-01版权所有：杨波，武汉科技大学理学院 n

14、语句的数量级：执行它的频数n算法的数量级：所有语句执行频数的和n算法的计算时间：（实际算法分析中）看成问题规模n的函数，记作T(n)。qn可以是输入量，输出量，或两者之和。qn可以是某种测度（数组的维数，图的边数等）2008-09-01版权所有：杨波，武汉科技大学理学院 例 1 下面是查找一维n元数组中最大元素的算法。该算法一次遍历数组中的每个元素，并保存当前的最大元素，被称为“最大元素顺序检索”。Public static int largest(int array,int n)int currlarge=0;for(int i=0;icurrlarge)currlarge=arrayi;r

15、eturn currlarge;2008-09-01版权所有：杨波，武汉科技大学理学院 分析方法：找近似时间n问题规模n（数组的维数）n基本运算，将存放的当前最大数与数组每个元素比较n假定每次比较的时间为cq变量i增加所需时间q找到一个新的最大元素时要做的工作q不考虑c的实际值，不考虑初始化时所需的一小部分时间，只想得到该算法的一个合理近似时间。计算时间T(n)=cn增长率：当问题规模增大时，算法代价增长的速度。线性增长率2008-09-01版权所有：杨波，武汉科技大学理学院 例 2 一个整数数组的第一个元素值复制给另一个变量。分析：n问题规模nn基本运算是赋值nT(n)=c1（c1表示赋值所

16、需时间），与问题规模无关。常数运行时间2008-09-01版权所有：杨波，武汉科技大学理学院 例 3 程序段如下：sum=0;for(i=1;i=n;i+)for(j=1;j=n;j+)sum+;分析：n问题规模nn基本运算是累加，时间c2（忽略初始化，循环变量的累加）nT(n)=c2 n2二次增长率2008-09-01版权所有：杨波，武汉科技大学理学院 T(n)的形式：n多项式增长率qT(n)=cqT(n)=cnqT(n)=cn2n指数增长率qT(n)=2nn对数增长率 qT(n)=logn2008-09-01版权所有：杨波，武汉科技大学理学院 最佳、最差和平均情况最佳、最差和平均情况例 从

17、一个n元数组中找出一个给定的K（假定数组中有且仅有一个元素值为K）。顺序检索法将从第一个元素开始，一次检索每一个元素，直到找到K为止，算法完成。最佳情况：检索1个元素最差情况：检索n个元素平均情况：检索n/2个元素算法分析时：n最佳情况一般不做研究。发生概率小，对于条件的考虑太乐观，不能作为算法性能的代表。n最差情况有必要。能知道算法至少能执行得多快，在实时系统中很重要n平均情况。算法的“典型”表现，适用于对许多不同的输入运行多次。但平均情况分析需考虑数据的分布情况。2008-09-01版权所有：杨波，武汉科技大学理学院 换一台更快的计算机，还是换一种更换一台更快的计算机，还是换一种更快的算法

18、？快的算法？f(n)nn变化n/n10n1,00010,000n=10n1020n5005,000n=10n105nlogn2501,842 n n 10n7.372n270223n=n3.162n1316n=n+3-规定时间内，速度是原来十倍的计算机所处理问题规模增长情况。假设原来的计算机能在一小时内完成10,000个基本操作。2008-09-01版权所有：杨波，武汉科技大学理学院 渐近分析渐近分析n渐近分析是指当输入规模很大，或者说达到极限（微积分意义上）时，对一种算法的研究。q计算时间或其他开销时，忽略系数。q注意力集中在重要的一点：增长率。q用于解决问题规模很大时的算法分析。q是对算法

19、资源开销的一种不精确的估算方法，它提供了对算法资源开销进行评估的简单化的模型。2008-09-01版权所有：杨波，武汉科技大学理学院 上限上限定义1：如果存在两个正常数c和n0，对于所有的nn0，有|T(n)|c|g(n)|则记作T(n)=O(g(n)说明：nT(n)表示算法的实际运行时间ng(n)是上限的一个函数表达式n常数n0是使上限成立的n的最小值n必须能找到一个常数c，而c确切是多少无关紧要n需考虑算法在最好，最坏和平均情况下的三种上限含义：n如果算法用n值不变的同一类数据在某台机器上运行时，所用的时间总是小于|g(n)|的一个常数倍。所以g(n)是计算时间T(n)的一个上界函数。T(

20、n)的数量级就是g(n)。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)2008-09-01版权所有：杨波，武汉科技大学理学院 多项式定理多项式定理 定理：若A(n)=amnm+a1n+a0是一个m次多项式，则有 A(n)=O(nm)即：变量n的固定阶数为m的任一多项式

21、，与此多项式的最高阶 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版权所有：杨波，武汉科技大学理学院 算法按时间的分类算法按时间的分类n多项式时间算法：可用多项式（函数）对其计算时间限界 的算法。常见的多项式限界函数有：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)n指数时间算法：计算时间用指数函数限界的算法 常

22、见的指数时间限界函数：O(2n)O(n！)0成立，则f(n)=O(g(n)；3.若f1(n)=O(g1(n)，f2(n)=O(g2(n)，则f1(n)+f2(n)=O(max(g1(n),g2(n)；4.若f1(n)=O(g1(n)，f2(n)=O(g2(n)，则f1(n)f2(n)=O(g1(n)g2(n)。法则1说明：如果g(n)是算法代价函数的一个上限，则g(n)的任意上限h(n)也是该算法代价的上限。对于表示法有类似的性质：若如果g(n)是算法代价函数的一个下限，则g(n)的任意下限h(n)也是该算法代价的下限。表示法同理。法则2的意义在于使我们能够忽略O表示法中的常数因子。对于和表示

23、法同样有这样的性质。法则3说明，顺序给出一个程序的两个部分（两组语句或两段代码），我们只需要考虑其中开销大的部分。类似地，在和表示法中，也只看开销大的部分就可以了。法则4用于分析程序中的简单循环。如果要有限次地重复某种操作，且每次重复的开销相等，则总开销为每次的开销与重复次数之积。对于和表示法结论也成立。2008-09-01版权所有：杨波，武汉科技大学理学院 可以在计算任何算法开销的近似增长率时，忽略所有的常数和低次项。2008-09-01版权所有：杨波，武汉科技大学理学院 程序运行时间的计算程序运行时间的计算例例1：首先看一个给整型变量赋值的简单语句：a=b；分析：该语句执行时间为一个常量，

24、为(1)。2008-09-01版权所有：杨波，武汉科技大学理学院 例例2：简单的循环：sum=0;for(i=1;i=n;i+)sum+=n;分析：n第一个语句时间代价为(1)nfor循环重复了n次n第三个语句时间代价为一常量n由法则4，后两行的for循环总时间代价为(n)n根据法则3，整个程序段时间代价为(n)。2008-09-01版权所有：杨波，武汉科技大学理学院 例例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;分析：n该程序段有三个相对独立的片断：一

25、个赋值语句和两个for循环结构。n赋值语句时间代价为常量，记作c1；n第二个for循环时间代价为c2n=(n)；n第一个for循环时间代价为 ，即(n2)；n根据法则3，总运行时间为(c1+c2n+c3n2)，可化简为(n2)。2008-09-01版权所有：杨波，武汉科技大学理学院 例例4：比较下面两段程序的算法分析：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版权

26、所有：杨波，武汉科技大学理学院 例例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;jb例2 考虑分析：a=1，b=3/2，c=1，d(n)=c2008-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

27、-1)-a2T(n-2)-akT(n-k)=0K阶常系数齐次差分方程的特征方程：xk-a1xk-1-a2xk-2-ak-1x-ak=02008-09-01版权所有：杨波，武汉科技大学理学院 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(

28、n-2)+akT(n-k)+f(n)，nk，ai，i=1,k为常数，ak0，f(n)0。K阶常系数非齐次差分方程：T(n)-a1T(n-1)-a2T(n-2)-akT(n-k)=f(n)通解是：对应齐次方程的通解特解2008-09-01版权所有：杨波，武汉科技大学理学院 n特解求法q试探法（因为并不存在寻找特解的一般方法）q根据f(n)的特点推测特解形式，用代定系数法确定系数。q利用叠加原理将f(n)线性分解成若干个单项之和，并求出各单项的特解，然后叠加得到f(n)的特解。这使得试探法更有效2008-09-01版权所有：杨波，武汉科技大学理学院 三种特殊形式的f(n)，其中pi,i=0,1,s

29、为待定的常数，c(x)为特征多项式。f(n)的形式条件特解形式anc(a)0p0ana是c(x)的m重根 p0nmannsc(1)0p0+p1n+p2n2+psns1是c(x)的m重根 nm(p0+p1n+p2n2+psns)nsanc(a)0(p0+p1n+p2n2+psns)ana是c(x)的m重根 nm(p0+p1n+p2n2+psns)an2008-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/

30、4 p2=17/24 p3=115/2882008-09-01版权所有：杨波，武汉科技大学理学院 例2 求解递归方程：解：c(x)=x2+5x+6=0 x1=-2 x2=-3 c(4)0 设T*(n)=p4n 得p=16 c1=-112 c2=962008-09-01版权所有：杨波，武汉科技大学理学院 生成函数（母函数）生成函数（母函数）定义：生成函数设a0,a1,an,是一个数列，做形式 幂级数：A(x)=a0+a1x+a2x2+anxn+称A(x)是数列a0,a1,an,的生成函数。2008-09-01版权所有：杨波，武汉科技大学理学院 n生成函数法基本思想q设定递归方程解的生成函数q努力

31、建立一个关于生成函数的可解方程，将其解出q返回递归方程的解n生成函数法的具体方法q由an定义生成函数A(x)，设对x的某些值A(x)收敛q根据递归方程作变换，求出A(x)的解析表达式q将A(x)重新展开成x的幂级数q展开式中的xn项系数就是序列的通项an的解析式2008-09-01版权所有：杨波，武汉科技大学理学院 例1：汉诺塔问题 设an表示移动n个盘子所需要的移动次数，根据递归算法递归方程为：2008-09-01版权所有：杨波，武汉科技大学理学院 生成函数的性质生成函数的性质n线性可加性：设G1(x)，G2(x)分别为ai，bi的生成函数，则c1G1(x)+c2G2(x)是c1ai+c2b

32、i的生成函数。n移位：设G(x)是ai的生成函数，则xnG(x)是n乘法：设G1(x)，G2(x)分别为ai，bi的生成函数，的生成函数则G1(x)G2(x)是的生成函数nx变换：设G(x)是ai的生成函数，则G(cx)是ciai的 生成函数2008-09-01版权所有：杨波，武汉科技大学理学院 生成函数的性质生成函数的性质n微分、积分的生成函数是是nan的生成函数2008-09-01版权所有：杨波，武汉科技大学理学院 例2：考虑线性变系数二阶齐次递归方程2008-09-01版权所有：杨波，武汉科技大学理学院 例3：二叉树的枚举n二叉树T和T相似：二者都空或二者都不为空树，且它们的左右子树都相似n二叉树T和T等价：二者不仅相似而且所有对应节点上的数据元素相同n二叉树枚举是讨论具有n个节点，互不相似的二叉树的数目bn2008-09-01版权所有：杨波，武汉科技大学理学院 例：当n=2时，不相似的二叉树有2棵，如下：例：当n=3时，不相似的二叉树有5棵，如下：2008-09-01版权所有：杨波，武汉科技大学理学院 n当n=0时，二叉树为空树，b0=1；n当n=1时，二叉树只有一个节点，b1=1；n当n=2时，b2=2；n当n=3时，b3=5；nbn的递归方程如下：2008-09-01版权所有：杨波，武汉科技大学理学院 2008-09-01版权所有：杨波，武汉科技大学理学院