算法设计与分析课件.ppt
《算法设计与分析课件.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析课件.ppt（351页珍藏版）》请在冰点文库上搜索。
1,主要内容介绍（续）,第7章概率算法第8章NP完全性理论第9章近似算法第10章算法优化策略,2,相关先导基础课程和算法概述,专业基础课程：
数据结构、计算机语言（C+）、操作系统如何编写计算机程序：
数据结构+算法=程序算法：
计算机软件的“灵魂”算法是计算机科学和计算机应用的核心,3,ACM国际大学生程序设计竞赛,ACM国际大学生程序设计竞赛（英文全称：
ACMInternationalCollegiateProgrammingContest（ACM-ICPC或ICPC）是由美国计算机协会（ACM）主办的，一项旨在展示大学生创新能力、团队精神和在压力下编写程序、分析和解决问题能力的年度竞赛。
经过30多年的发展，ACM国际大学生程序设计竞赛已经发展成为最具影响力的大学生计算机竞赛。
赛事目前由IBM公司赞助。
4,内容,入门三本：
数据结构与算法（傅清祥，王晓东编著）程序设计导引及在线实践作者:
李文新ACM程序设计培训教程吴昊基础提高：
算法艺术与信息学竞赛第二版刘汝佳余祥宣等编著，计算机算法基础（第三版），华中理工大学出版社科曼：
算法导论组合数学第三版冯舜玺译计算几何算法设计与分析周培德数据结构（C+语言描述）朱战立组合数学的算法与程序设计程序设计中的组合数学吴文虎图论的算法与程序设计,5,教材与参考书,教材：
算法设计与分析（第三版）王晓东，2007年5月，电子工业出版社。
参考书：
徐士良编，C常用算法程序集，华大学出版社，1998年霍红卫编，算法设计与分析西安电子科技大学出版社，2005年卢开澄编，计算机算法导引，清华大学出版社，2003年,6,部分目录,第1章算法概述1.1算法与程序1.2算法复杂性分析第2章递归与分治策略2.1递归的概念2.2分治法的基本思想2.3二分搜索技术2.4大整数的乘法2.5Strassen矩阵乘法2.6棋盘覆盖2.7合并排序2.8快速排序2.9线性时间选择2.10最接近点对问题2.11循环赛日程表,第3章动态规划3.1矩阵连乘问题3.2动态规划算法的基本要素3.3最长公共子序列3.4最大子段和3.5凸多边形最优三角剖分3.6多边形游戏3.7图像压缩3.8电路布线3.9流水作业调度3.100-1背包问题3.11最优二叉搜索树3.12动态规划加速原理第4章贪心算法第5章回溯法第6章分支限界法第7章随机化算法第8章线性规划与网络流第9章NP完全性理论与近似算法,7,第1章算法概述,理解算法的概念理解什么是程序，程序和算法的区别和内在联系能够列举求解问题的基本步骤掌握算法复杂性的渐进性态的数学表达式掌握三种计算复杂性概念掌握C+语言描述算法的方法,本章主要知识点：
8,1.1算法与程序,输入：
有零个或多个外部量作为算法的输入。
输出：
算法产生至少一个量作为输出。
确定性：
组成算法的每条指令清晰、无歧义。
有限性：
算法中每条指令的执行次数有限，执行每条指令的时间也有限。
是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质（4）即有限性。
是满足下述性质的指令序列。
算法：
程序：
9,算法学习的内容,如何设计算法：
设计策略，创造性的活动如何表示算法自然语言流程图伪码程序语言如何确认算法：
证明算法的正确性如何分析算法：
时间和空间需求的定量分析如何测试算法调试：
“调试只能指出有错误，而不能指出它们不存在错误”作时空分布图：
验证分析结论，优化算法设计,10,1.2算法复杂性分析,算法分析对算法所消耗的资源（时间和空间）进行估算算法分析的目的预计所涉及的算法能在什么样的环境中有效地运行，在最好、最坏和平均情况下执行得怎么样。
对同一问题的不同算法进行时空耗费两方面的分析算法分析的意义通过对算法的分析，在把算法变成程序实际运行前，就知道为完成一项任务所设计的算法的好坏，从而运行好的算法，改进差的算法，避免无益的人力和物力浪费。
算法分析是计算机领域的“古老”而“前沿”的课题。
11,1.2算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F（N,I,A）。
一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：
T=T（N,I）和S=S（N,I）。
（通常，让A隐含在复杂性函数名当中）,12,1.2算法复杂性分析,最坏情况下的时间复杂性：
最好情况下的时间复杂性：
平均情况下的时间复杂性：
其中DN是规模为N的合法输入的集合；I*是DN中使T（N,I*）达到Tmax（N）的合法输入；是中使T（N,）达到Tmin（N）的合法输入；而P（I）是在算法的应用中出现输入I的概率。
13,1.2算法复杂性分析,算法复杂性在渐近意义下的阶：
渐近意义下的记号：
O、o设f（N）和g（N）是定义在正数集上的正函数。
O的定义：
如果存在正的常数C和自然数N0，使得当NN0时有f（N）Cg（N），则称函数f（N）当N充分大时上有界，且g（N）是它的一个上界，记为f（N）=O（g（N）。
即f（N）的阶不高于g（N）的阶。
根据O的定义，容易证明它有如下运算规则：
（1）O（f）+O（g）=O（max（f,g）；
（2）O（f）+O（g）=O（f+g）；（3）O（f）O（g）=O（fg）；（4）如果g（N）=O（f（N），则O（f）+O（g）=O（f）；（5）O（Cf（N）=O（f（N），其中C是一个正的常数；（6）f=O（f）。
14,1.2算法复杂性分析,的定义：
如果存在正的常数C和自然数N0，使得当NN0时有f（N）Cg（N），则称函数f（N）当N充分大时下有界，且g（N）是它的一个下界，记为f（N）=（g（N）。
即f（N）的阶不低于g（N）的阶。
的定义：
定义f（N）=（g（N）当且仅当f（N）=O（g（N）且f（N）=（g（N）。
此时称f（N）与g（N）同阶。
o的定义：
对于任意给定的0，都存在正整数N0，使得当NN0时有f（N）/Cg（N）,则称函数f（N）当N充分大时的阶比g（N）低，记为f（N）=o（g（N）。
例如，4NlogN+7=o（3N2+4NlogN+7）。
15,算法按时间的分类,多项式时间算法：
可用多项式（函数）对其计算时间限界的算法。
常见的多项式限界函数有：
O
（1）O（logn）O（n）O（nlogn）O（n2）O（n3）指数时间算法：
计算时间用指数函数限界的算法常见的指数时间限界函数：
O（2n）O（n！
）O（nn）说明：
当n取值较大时，指数时间算法和多项式时间算法在计算时间上非常悬殊。
16,典型的计算时间函数曲线,17,第一章作业,课后练习：
1-1;1-3：
补充题目：
1，冒泡排序的最好，最坏情况的元素比较和原始元素排列是什么？
2，100n2和2n，使前者快于后者，n最小值是多少?
18,第2章递归与分治策略,19,将要求解的较大规模的问题分割成k个更小规模的子问题。
算法总体思想,n,T（n/2）,T（n/2）,T（n/2）,T（n/2）,T（n）,=,对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
20,算法总体思想,对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
n,T（n）,=,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
21,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
n,T（n）,=,22,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
凡治众如治寡，分数是也。
-孙子兵法,23,2.1递归的概念,直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
下面来看几个实例。
24,2.1递归的概念,例1阶乘函数阶乘函数可递归地定义为：
边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
25,2.1递归的概念,例2Fibonacci数列无穷数列1，1，2，3，5，8，13，21，34，55，被称为Fibonacci数列。
它可以递归地定义为：
边界条件,递归方程,第n个Fibonacci数可递归地计算如下：
publicstaticintfibonacci（intn）if（n=1）return1;returnfibonacci（n-1）+fibonacci（n-2）;,26,27,2.1递归的概念,例3Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。
Ackerman函数A（n，m）定义如下：
28,2.1递归的概念,例3Ackerman函数前2例中的函数都可以找到相应的非递归方式定义：
但本例中的Ackerman函数却无法找到非递归的定义。
29,2.1递归的概念,例3Ackerman函数A（n，m）的自变量m的每一个值都定义了一个单变量函数：
M=0时，A（n,0）=n+2M=1时，A（n,1）=A（A（n-1,1）,0）=A（n-1,1）+2，和A（1,1）=2故A（n,1）=2*nM=2时，A（n,2）=A（A（n-1,2）,1）=2A（n-1,2），和A（1,2）=A（A（0,2）,1）=A（1,1）=2，故A（n,2）=2n。
M=3时，类似的可以推出M=4时，A（n,4）的增长速度非常快，以至于没有适当的数学式子来表示这一函数。
30,2.1递归的概念,例3Ackerman函数定义单变量的Ackerman函数A（n）为，A（n）=A（n，n）。
定义其拟逆函数（n）为：
（n）=minkA（k）n。
即（n）是使nA（k）成立的最小的k值。
（n）在复杂度分析中常遇到。
对于通常所见到的正整数n，有（n）4。
但在理论上（n）没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。
31,2.1递归的概念,例4排列问题设计一个递归算法生成n个元素r1,r2,rn的全排列。
设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。
集合X中元素的全排列记为perm（X）。
（ri）perm（X）表示在全排列perm（X）的每一个排列前加上前缀得到的排列。
R的全排列可归纳定义如下：
当n=1时，perm（R）=（r），其中r是集合R中唯一的元素；当n1时，perm（R）由（r1）perm（R1），（r2）perm（R2），（rn）perm（Rn）构成。
32,2.1递归的概念,例5整数划分问题将正整数n表示成一系列正整数之和：
n=n1+n2+nk，其中n1n2nk1，k1。
正整数n的这种表示称为正整数n的划分。
求正整数n的不同划分个数。
例如正整数6有如下11种不同的划分：
6；5+1；4+2，4+1+1；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。
33,
（2）q（n,m）=q（n,n）,mn;最大加数n1实际上不能大于n。
因此，q（1,m）=1。
（1）q（n,1）=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即,（4）q（n,m）=q（n,m-1）+q（n-m,m）,nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1的划分组成。
（3）q（n,n）=1+q（n,n-1）;正整数n的划分由n1=n的划分和n1n-1的划分组成。
2.1递归的概念,例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设p（n）为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：
将最大加数n1不大于m的划分个数记作q（n,m）。
可以建立q（n,m）的如下递归关系。
34,2.1递归的概念,例5整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设p（n）为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：
将最大加数n1不大于m的划分个数记作q（n,m）。
可以建立q（n,m）的如下递归关系。
正整数n的划分数p（n）=q（n,n）。
35,36,2.1递归的概念,例6Hanoi塔问题设a,b,c是3个塔座。
开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。
各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。
在移动圆盘时应遵守以下移动规则：
规则1：
每次只能移动1个圆盘；规则2：
任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：
在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。
37,在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。
当n=1时，问题比较简单。
此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。
当n1时，需要利用塔座c作为辅助塔座。
此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。
由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。
由此可以设计出解Hanoi塔问题的递归算法如下。
2.1递归的概念,例6Hanoi塔问题,publicstaticvoidhanoi（intn,inta,intb,intc）if（n0）hanoi（n-1,a,c,b）;move（a,b）;hanoi（n-1,c,b,a）;,思考题：
如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不变，求移动步数最小的方案。
38,递归小结,优点：
结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：
递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。
39,递归小结,解决方法：
在递归算法中消除递归调用，使其转化为非递归算法。
1.采用一个用户定义的栈来模拟系统的递归调用工作栈。
该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。
2.用递推来实现递归函数。
3.通过Cooper变换、反演变换能将一些递归转化为尾递归，从而迭代求出结果。
后两种方法在时空复杂度上均有较大改善，但其适用范围有限。
40,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：
该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。
这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。
这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。
41,分治法的基本步骤,divide-and-conquer（P）if（|P|=n0）adhoc（P）;/解决小规模的问题dividePintosmallersubinstancesP1,P2,.,Pk；/分解问题for（i=1,i=k,i+）yi=divide-and-conquer（Pi）;/递归的解各子问题returnmerge（y1,.,yk）;/将各子问题的解合并为原问题的解人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。
即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。
这种使子问题规模大致相等的做法是出自一种平衡（balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。
42,分治法的复杂性分析,一个分治法将规模为n的问题分成k个规模为nm的子问题去解。
设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。
再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f（n）个单位时间。
用T（n）表示该分治法解规模为|P|=n的问题所需的计算时间，则有：
通过迭代法求得方程的解：
注意：
递归方程及其解只给出n等于m的方幂时T（n）的值，但是如果认为T（n）足够平滑，那么由n等于m的方幂时T（n）的值可以估计T（n）的增长速度。
通常假定T（n）是单调上升的，从而当minmi+1时，T（mi）T（n）T（mi+1）。
43,二分搜索技术,分析：
如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。
因此这个问题满足分治法的第一个适用条件,分析：
比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。
无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不过是查找的规模缩小了。
这就说明了此问题满足分治法的第二个和第三个适用条件。
分析：
很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。
给定已按升序排好序的n个元素a0:
n-1，现要在这n个元素中找出一特定元素x。
分析：
该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。
44,二分搜索技术,给定已按升序排好序的n个元素a0:
n-1，现要在这n个元素中找出一特定元素x。
据此容易设计出二分搜索算法：
publicstaticintbinarySearch（inta,intx,intn）/在a0amiddle）left=middle+1;elseright=middle-1;return-1;/未找到x,算法复杂度分析：
每执行一次算法的while循环，待搜索数组的大小减少一半。
因此，在最坏情况下，while循环被执行了O（logn）次。
循环体内运算需要O
（1）时间，因此整个算法在最坏情况下的计算时间复杂性为O（logn）。
思考题：
给定a，用二分法设计出求an的算法。
45,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：
O（n2）效率太低分治法:
a,b,c,d,复杂度分析T（n）=O（n2）没有改进,X=Y=X=a2n/2+bY=c2n/2+dXY=ac2n+（ad+bc）2n/2+bd,46,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：
O（n2）效率太低分治法:
XY=ac2n+（ad+bc）2n/2+bd为了降低时间复杂度，必须减少乘法的次数。
XY=ac2n+（a-c）（b-d）+ac+bd）2n/2+bdXY=ac2n+（a+c）（b+d）-ac-bd）2n/2+bd,复杂度分析T（n）=O（nlog3）=O（n1.59）较大的改进,细节问题：
两个XY的复杂度都是O（nlog3），但考虑到a+c,b+d可能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。
47,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：
O（n2）效率太低分治法:
O（n1.59）较大的改进更快的方法?
如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。
最终的，这个思想导致了快速傅利叶变换（FastFourierTransform）的产生。
该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O（nlogn）时间内解决。
是否能找到线性时间的算法？
目前为止还没有结果。
48,Strassen矩阵乘法,A和B的乘积矩阵C中的元素Ci,j定义为:
若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。
因此，算出矩阵C的个元素所需的计算时间为O（n3）,传统方法：
O（n3）,49,Strassen矩阵乘法,使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。
由此可将方程C=AB重写为：
传统方法：
O（n3）分治法:
由此可得：
复杂度分析T（n）=O（n3）没有改进,50,Strassen矩阵乘法,传统方法：
O（n3）分治法:
为了降低时间复杂度，必须减少乘法的次数。
复杂度分析T（n）=O（nlog7）=O（n2.81）较大的改进,51,Strassen矩阵乘法,传统方法：
O（n3）分治法:
O（n2.81）更快的方法?
Hopcroft和Kerr已经证明（1971），计算2个矩阵的乘积，7次乘法是必要的。
因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。
或许应当研究或矩阵的更好算法。
在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。
目前最好的计算时间上界是O（n2.376）是否能找到O（n2）的算法？
目前为止还没有结果。
52,棋盘覆盖,在一个2k2k个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
53,棋盘覆盖,当k0时，将2k2k棋盘分割为4个2k-12k-1子棋盘（a）所示。
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。
为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如（b）所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。
递归地使用这种分割，直至棋盘简化为棋盘11。
54,棋盘覆盖,publicvoidchessBoard（inttr,inttc,intdr,intdc,intsize）if（size=1）return;intt=tile+,/L型骨牌号s=size/2;/分割棋盘/覆盖左上角子棋盘if（dr=tc+s）/特殊方格在此棋盘中chessBoard（tr,tc+s,dr,dc,s）;else/此棋盘中无特殊方格/用t号L型骨牌覆盖左下角,boardtr+s-1tc+s=t;/覆盖其余方格chessBoard（tr,tc+s,tr+s-1,tc+s,s）;/覆盖左下角子棋盘if（dr=tr+s,复杂度分析T（n）=O（4k）渐进意义下的最优算法,55,合并排序,基本思想：
将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。
publicstaticvoidmergeSort（Comparablea,intleft,intrig
升级会员 