算法设计与分析 全套课件.ppt
《算法设计与分析 全套课件.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析 全套课件.ppt（378页珍藏版）》请在冰点文库上搜索。
中国计算机学会21世纪大学本科计算机专业系列教材算法设计与分析,王晓东编著,巢湖学院计算机科学与技术系,主要内容介绍,第1章、算法引论第2章、递归与分治策略第3章、动态规划第4章、贪心算法第5章、回溯法第6章、分支限界法第7章、概率算法第8章、NP完全性理论第9章、近似算法第10章、算法优化策略,巢湖学院计算机科学与技术系,第1章算法引论,1.1算法与程序1.2表达算法的抽象机制1.3描述算法1.4算法复杂性分析,本章主要知识点：
巢湖学院计算机科学与技术系,1.1、算法与程序,算法：
是指解决问题的一种方法或一个过程，在计算机领域是指满足下述性质的指令序列。
（1）输入：
有外部提供的量作为算法的输入。
（2）输出：
算法产生至少一个量作为输出。
（3）确定性：
组成算法的每条指令是清晰，无歧义的。
（4）有限性：
算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。
巢湖学院计算机科学与技术系,1.1、算法与程序,程序：
是算法用某种程序设计语言的具体实现。
程序可以不满足算法的性质（4）。
例如操作系统，是一个在无限循环中执行的程序，因而不是一个算法。
操作系统的各种任务可看成是单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现。
该子程序得到输出结果后便终止。
巢湖学院计算机科学与技术系,问题求解（ProblemSolving）,理解问题,精确解或近似解选择数据结构算法设计策略,设计算法,巢湖学院计算机科学与技术系,1.从机器语言到高级语言的抽象,1.2、表达算法的抽象机制,高级程序设计语言的主要好处是：
（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。
（1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需要几周时间的培训就可以胜任程序员的工作；,
（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；,（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；,巢湖学院计算机科学与技术系,2.抽象数据类型,1.2、表达算法的抽象机制,抽象数据类型是算法的一个数据模型连同定义在该模型上，并作为算法构件的一组运算。
抽象数据类型带给算法设计的好处有：
（1）算法顶层设计与底层实现分离；
（2）算法设计与数据结构设计隔开，允许数据结构自由选择；（3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷；（4）用抽象数据类型表述的算法具有很好的可维护性；（5）算法自然呈现模块化；（6）为自顶向下逐步求精和模块化提供有效途径和工具；（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。
巢湖学院计算机科学与技术系,1.3、算法复杂性分析,算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性T（N），需要的空间资源的量称为空间复杂性S（N）。
这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。
如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F（N,I,A）。
一般把时间复杂性和空间复杂性分开，分别用T和S来表示则有：
T=T（N,I）和S=S（N,I）。
（通常，让A隐含在复杂性函数名当中）,巢湖学院计算机科学与技术系,1.3、算法复杂性分析,最坏情况下的时间复杂性：
最好情况下的时间复杂性：
平均情况下的时间复杂性：
其中DN是规模为N的合法输入的集合；I*是DN中使T（N,I*）达到Tmax（N）的合法输入；是中使T（N,）达到Tmin（N）的合法输入；而P（I）是在算法的应用中出现输入I的概率。
巢湖学院计算机科学与技术系,1.3、算法复杂性分析,算法复杂性在渐近意义下的阶：
渐近意义下的记号：
O、o设f（N）和g（N）是定义在正数集上的正函数。
（1）渐近上界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（f*g）；（4）如果g（N）=O（f（N），则O（f）+O（g）=O（f）；（5）O（Cf（N）=O（f（N），其中C是一个正的常数；（6）f=O（f）。
巢湖学院计算机科学与技术系,1.3、算法复杂性分析,
（2）渐近下界的定义：
如果存在正的常数C和自然数N0，使得当NN0时有f（N）Cg（N），则称函数f（N）当N充分大时下有界，且g（N）是它的一个下界，记为f（N）=（g（N）。
即f（N）的阶不低于g（N）的阶。
（3）同阶的定义：
定义f（N）=（g（N）当且仅当f（N）=O（g（N）且f（N）=（g（N），即（g（n）=f（n）|存在正常数c1,c2和正整数n0使得对所有nn0有：
c1g（n）f（n）c2g（n），此时称f（N）与g（N）同阶。
定理1：
（g（n）=O（g（n）（g（n）,巢湖学院计算机科学与技术系,1.3、算法复杂性分析,（4）低阶o的定义：
对于任意给定的0，都存在正整数N0，使得当NN0时有f（N）/Cg（N）,则称函数f（N）当N充分大时的阶比g（N）低，记为f（N）=o（g（N）。
（有的书称之为非紧上界）例如，4NlogN+7=o（3N2+4NlogN+7）。
（5）非紧下界记号（g（n）=f（n）|对于任何正常数c0，存在正数和n00使得对所有nn0有：
0cg（n）f（n）。
注意：
f（n）（g（n）g（n）o（f（n）,巢湖学院计算机科学与技术系,渐近分析记号在等式和不等式中的意义,f（n）=（g（n）的确切意义是：
f（n）（g（n）。
一般情况下，等式和不等式中的渐近记号（g（n）表示（g（n）中的某个函数。
例如：
2n2+3n+1=2n2+（n）表示2n2+3n+1=2n2+f（n），其中f（n）是（n）中某个函数。
等式和不等式中渐近记号O,o,和的意义是类似的。
巢湖学院计算机科学与技术系,渐近分析中函数比较,f（n）=O（g（n）ab;f（n）=（g（n）ab;f（n）=（g（n）a=b;f（n）=o（g（n）ab;,巢湖学院计算机科学与技术系,渐近分析记号的若干性质,
（1）传递性：
f（n）=（g（n），g（n）=（h（n）f（n）=（h（n）；f（n）=O（g（n），g（n）=O（h（n）f（n）=O（h（n）；f（n）=（g（n），g（n）=（h（n）f（n）=（h（n）；f（n）=o（g（n），g（n）=o（h（n）f（n）=o（h（n）；f（n）=（g（n），g（n）=（h（n）f（n）=（h（n）；
（2）反身性：
f（n）=（f（n）；f（n）=O（f（n）；f（n）=（f（n）.（3）对称性：
f（n）=（g（n）g（n）=（f（n）.（4）互对称性：
f（n）=O（g（n）g（n）=（f（n）；f（n）=o（g（n）g（n）=（f（n）；,巢湖学院计算机科学与技术系,（5）算术运算：
O（f（n）+O（g（n）=O（maxf（n）,g（n）；O（f（n）+O（g（n）=O（f（n）+g（n）；O（f（n）*O（g（n）=O（f（n）*g（n）；O（cf（n）=O（f（n）；g（n）=O（f（n）O（f（n）+O（g（n）=O（f（n）。
渐近分析记号的若干性质,巢湖学院计算机科学与技术系,规则O（f（n）+O（g（n）=O（maxf（n）,g（n）的证明：
对于任意f1（n）O（f（n），存在正常数c1和自然数n1，使得对所有nn1，有f1（n）c1f（n）。
类似地，对于任意g1（n）O（g（n），存在正常数c2和自然数n2，使得对所有nn2，有g1（n）c2g（n）。
令c3=maxc1,c2,n3=maxn1,n2,h（n）=maxf（n）,g（n）。
则对所有的nn3，有f1（n）+g1（n）c1f（n）+c2g（n）c3f（n）+c3g（n）=c3（f（n）+g（n）c32maxf（n）,g（n）=2c3h（n）=O（maxf（n）,g（n）.,渐近分析记号的若干性质,巢湖学院计算机科学与技术系,算法渐近复杂性分析中常用函数,
（1）单调函数单调递增：
mnf（m）f（n）;单调递减：
mnf（m）f（n）;严格单调递增：
mf（n）.
（2）取整函数x：
不大于x的最大整数；x：
不小于x的最小整数；,巢湖学院计算机科学与技术系,取整函数的若干性质,x-1xxxx+1；n/2+n/2=n;对于n0，a,b是大于0的整数，有：
n/a/b=n/ab;n/a/b=n/ab;a/b（a+（b-1）/b;a/b（a-（b-1）/b;f（x）=x,g（x）=x为单调递增函数。
巢湖学院计算机科学与技术系,（3）多项式函数p（n）=a0+a1n+a2n2+adnd；ad0;p（n）=（nd）;f（n）=O（nk）f（n）多项式有界；f（n）=O
（1）f（n）c;kdp（n）=O（nk）;kdp（n）=（nk）;kdp（n）=o（nk）;kdp（n）=（nk）.,算法渐近复杂性分析中常用函数,巢湖学院计算机科学与技术系,算法渐近复杂性分析中常用函数,（4）指数函数对于正整数m,n和实数a0:
a0=1;a1=a;a-1=1/a;（am）n=amn;（am）n=（an）m;aman=am+n;a1an为单调递增函数;a1nb=o（an）,巢湖学院计算机科学与技术系,算法渐近复杂性分析中常用函数,（5）对数函数logn=log2n;lgn=log10n;lnn=logen;logkn=（logn）k;loglogn=log（logn）;fora0,b0,c0,巢湖学院计算机科学与技术系,|x|1forx-1,foranya0,logbn=o（na）,算法渐近复杂性分析中常用函数,（5）对数函数,巢湖学院计算机科学与技术系,算法渐近复杂性分析中常用函数,（6）阶层函数Stirlingsapproximation,巢湖学院计算机科学与技术系,算法分析中常见的复杂性函数,巢湖学院计算机科学与技术系,小规模数据,巢湖学院计算机科学与技术系,中等规模数据,巢湖学院计算机科学与技术系,
（1）选择语句：
（1.1）if语句：
（1.2）？
语句：
if（expression）statement;elsestatement;,exp1?
exp2:
exp3y=x9?
100:
200;等价于：
if（x9）y=100;elsey=200;,用c+描述算法的常用语句,巢湖学院计算机科学与技术系,switch（expression）case1:
statementsequence;break;case2:
statementsequence;break;default:
statementsequence;,（1.3）switch语句：
用c+描述算法的常用语句,巢湖学院计算机科学与技术系,（2.1）for循环：
for（init;condition;inc）statement;（2.2）while循环：
while（condition）statement;（2.3）do-while循环：
dostatement;while（condition）;,用c+描述算法的常用语句,
（2）迭代语句,巢湖学院计算机科学与技术系,（3.1）return语句：
returnexpression;（3.2）goto语句：
gotolabel;label:
用c+描述算法的常用语句,（3）跳转语句：
巢湖学院计算机科学与技术系,算法分析方法举例,例：
顺序搜索算法,templateintseqSearch（Type*a,intn,Typek）for（inti=0;in;i+）if（ai=k）returni;return-1;,巢湖学院计算机科学与技术系,
（1）Tmax（n）=maxT（I）|size（I）=n=O（n）
（2）Tmin（n）=minT（I）|size（I）=n=O
（1）（3）在平均情况下，假设：
（a）搜索成功的概率为p（0p1）；（b）在数组的每个位置i（0in）搜索成功的概率相同，均为p/n。
算法分析方法举例,巢湖学院计算机科学与技术系,算法分析的基本法则,
（一）非递归算法：
（1）for/while循环循环体内计算时间*循环次数；
（2）嵌套循环循环体内计算时间*所有循环次数；（3）顺序语句各语句计算时间相加；（4）if-else语句if语句计算时间和else语句计算时间的较大者。
巢湖学院计算机科学与技术系,templatevoidinsertion_sort（Type*a,intn）Typekey;/costtimesfor（inti=1;i=0/c7n-1,巢湖学院计算机科学与技术系,在最好情况下，ti=1,for1in;在最坏情况下，tii+1,for1in;,巢湖学院计算机科学与技术系,对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort达到其最坏情形。
因此：
由此可见，Tmax（n）=（n2）,巢湖学院计算机科学与技术系,
（二）递归算法复杂性分析,intfactorial（intn）if（n=0）return1;returnn*factorial（n-1）;,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型1,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型2,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型3,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型4,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型5,巢湖学院计算机科学与技术系,递归算法复杂性分析和递归方程的解,类型6,巢湖学院计算机科学与技术系,递归方程组解的渐进阶的求法套用公式法,这个方法为估计形如：
T（n）=aT（n/b）+f（n）
（1）的递归方程解的渐近阶提供三个可套用的公式。
（1）中的a1和b1是常数，f（n）是一个确定的正函数。
（1）是一类分治法的时间复杂性所满足的递归关系，即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。
如果用T（n）表示规模为n的原问题的复杂性，用f（n）表示把原问题分成a个子问题和将a个子问题的解综合为原问题的解所需要的时间，我们便有方程
（1）。
巢湖学院计算机科学与技术系,递归方程组解的渐进阶的求法套用公式法,设a1和b1是常数,f（n）是定义在非负整数上的一个确定的非负函数。
又设T（n）也是定义在非负整数上的一个非负函数，且满足递归方程
（1）。
方程
（1）中的n/b可以是n/b，也可以是n/b。
那么，在f（n）的三类情况下，我们有T（n）的渐近估计式：
若对于某常数0，有则:
巢湖学院计算机科学与技术系,递归方程组解的渐进阶的求法套用公式法,若则,巢湖学院计算机科学与技术系,递归方程组解的渐进阶的求法套用公式法,若:
对于某常数0，有且对于某常数c1和所有充分大的正整数n有af（n/b）cf（n）;则T（n）=（f（n）,巢湖学院计算机科学与技术系,（三）最优算法,问题的计算时间下界为（f（n），则计算时间复杂性为O（f（n）的算法是最优算法。
例如，排序问题的计算时间下界为（nlogn），计算时间复杂性为O（nlogn）的排序算法是最优算法。
堆排序算法是最优算法。
巢湖学院计算机科学与技术系,第一章：
作业布置,书面作业：
P5：
算法分析题1-1、1-3、1-6（1、3、5、7）；,上机练习（多选一）：
P6-7：
算法实现题1-1、1-3；,第2章、递归与分治策略,巢湖学院计算机科学与技术系,将要求解的较大规模的问题分割成k个更小规模的子问题。
算法总体思想,n,T（n/2）,T（n/2）,T（n/2）,T（n/2）,T（n）,=,对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
巢湖学院计算机科学与技术系,算法总体思想,对这k个子问题分别求解。
如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。
n,T（n）,=,巢湖学院计算机科学与技术系,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
n,T（n）,=,巢湖学院计算机科学与技术系,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
分治法的设计思想是:
将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
凡治众如治寡，分数是也。
-孙子兵法,巢湖学院计算机科学与技术系,2.1、递归的概念,直接或间接地调用自身的算法称为递归算法。
用函数自身给出定义的函数称为递归函数。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
下面来看几个实例。
巢湖学院计算机科学与技术系,2.1、递归的概念,例1:
阶乘函数阶乘函数可递归地定义为：
边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。
巢湖学院计算机科学与技术系,2.1、递归的概念,例2:
Fibonacci数列无穷数列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）;,巢湖学院计算机科学与技术系,2.1、递归的概念,例3:
Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。
Ackerman函数A（n，m）定义如下：
巢湖学院计算机科学与技术系,2.1、递归的概念,例3:
Ackerman函数前2例中的函数都可以找到相应的非递归方式定义：
但本例中的Ackerman函数却无法找到非递归的定义。
巢湖学院计算机科学与技术系,2.1、递归的概念,例3:
Ackerman函数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）的增长速度非常快，以至于没有适当的数学式子来表示这一函数。
巢湖学院计算机科学与技术系,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的增加，它以难以想象的慢速度趋向正无穷大.,巢湖学院计算机科学与技术系,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）构成;,巢湖学院计算机科学与技术系,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。
巢湖学院计算机科学与技术系,
（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）的如下递归关系。
巢湖学院计算机科学与技术系,2.1、递归的概念,例5、整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。
在本例中，如果设p（n）为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：
将最大加数n1不大于m的划分个数记作q（n,m）。
可以建立q（n,m）的如下递归关系。
正整数n的划分数p（n）=q（n,n）。
巢湖学院计算机科学与技术系,2.1、递归的概念,例6Hanoi塔问题设a,b,c是3个塔座。
开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。
各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。
在移动圆盘时应遵守以下移动规则：
规则1:
每次只能移动1个圆盘；规则2:
任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3:
在满足移动规则1和2的前提下,可将圆盘移至a,b,c中任一塔座上。
巢湖学院计算机科学与技术系,当n=1时，问题比较简单。
此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。
当n1时，需要利用塔座c作为辅助塔座。
此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。
由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。
由此可以设计出解Hanoi塔问题的递归算法如下。
例6、Hanoi塔问题在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。
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，移动规则不变，求移
升级会员 