算法设计与分析PPT课件

算法设计与分析2课程目的对算法设计与分析进行一个较为全面的介绍，使大家具有进行简单的算法设计与分析的基本能力先修课程程序设计语言数据结构高等数学离散数学概率论3主要内容介绍第1章算法引论第2章递归与分治策略第3章动态规划第4章贪心算法第5章回溯法第6章分支限界法第7章概率算法第8章NP完全性理论4教学用书王晓东算法设计与分析清华大学出版社5T.Cormen,C.Leiserson,R.Rivest,andC.SteinIntroductiontoAlgorithms,2ndEd.MITPressandMcGraw-HillBookCompany,2001教学参考书6D.E.KnuthTheArtofComputerProgramming,Vol.1and3,ThirdEdition,AddisonWesley,1997.7第1章算法引论程序=算法+数据结构1.1算法与程序一.算法在计算机科学中的重要地位8二.算法的基本概念一个有穷规则的有序集合称为一个算法。1.定义.2.算法的特征.输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限。可行性：执行每条指令的时间也有限。9例.求正整数m、n的最大公因数。解一.（1）求余数：用m除以n，得余数r(0≤r﹤n)。（2）判断余数：若余数r=0，输出n，结束。否则，转（3）。（3）更新被除数和除数：m←n，n←r，转(1)。10解二.开始输入m、nr=m%nr=0?m←n，n←r输出n是否11解三.Euclid(intm,intn){intr;while(n!=0){r=m%n;m=n;n=r;}printf(“%d”,m)}123.算法的描述方法.（1）自然语言（2）流程图（3）程序设计语言13三.算法设计与分析的步骤1.问题的描述.2.模型的选择.3.算法设计和正确性证明.4.算法的分析.5.算法的实现.141.2算法复杂性分析算法复杂性是算法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用n、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(n,I,A)。一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有：T=T(n,I)和S=S(n,I)。（通常，让A隐含在复杂性函数名当中）15最坏情况下的时间复杂度：),(max)(maxInTnTnDI),(*1Inetkiii),(*InT渐近时间复杂度：平均情况下的时间复杂性：nDIInTIPnT),()()(avgnDIkiiiInetIP),()(1设Dn是规模为n的合法输入的集合；I*是Dn中使T(n,I*)达到Tmax(n)的合法输入；而P(I)是在算法的应用中出现输入I的概率。则：n→∞时，T(n)的主要部分算法共有k种基本步骤，第i种步骤所需时间ti，出现次数ei.用问题体积n表示的运行时间T(n)称为时间复杂度)(nT16算法复杂度的重要性假设计算机每秒可作1000次基本运算17有效算法最佳算法计算问题的分类1.无法写出算法的问题.2.有多项式算法的问题.3.介于上述两问题之间的问题.18例之值。求0111)(axaxaxaxPnnnnn解用最直观的方法2)1()121()(nnnnnT用Horner算法01321)))))((((()(axaxaxaaxaxPnnnnnnnT)(Horner(inta[n+1],realx){intp=a[n];for(i=1;i=n;i++)p=p*x+a[n-i];returnp;}19表示算法渐近复杂度的数学符号：渐近意义下的记号：O、Ω、θ、o设f(n)和g(n)是定义在正数集上的正函数。O的定义：如果存在正的常数C和自然数N0，使得当nN0时有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=O(f)，则O(f)+O(g)=O(f)；(5)O(Cf)=O(f)，其中C是一个正的常数；(6)f=O(f)。20Ω的定义：如果存在正的常数C和自然数N0，使得当nN0时有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，使得当nN0时有f(n)/g(n)ε,则称函数f(n)当n充分大时的阶比g(n)低，记为f(n)=o(g(n))。例如，4nlogn+7=o(3n2+4nlogn+7)。21第2章递归与分治策略凡治众如治寡，分数是也。----孙子兵法222.1递归的概念直接或间接地调用自身的较小模式的算法称为递归算法。用函数自身的较小模式给出其定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，子问题的复杂度也原问题复杂度的较小模式，这就为使用递归技术进行算法分析提供了方便。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。23例1阶乘函数阶乘函数可递归地定义为：00)!1(1!nnnnn边界条件递归方程边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。下面来看几个实例:factorial(intn){if(n=0)return1;elsereturnfactorial(n-1);}T(n)=T(n-1)+1,T(n)=O(n)24nnn)1(321!阶乘函数可以找到相应的非递归方式定义：factorial(intn){inti,p=1;for(i=1;i=n;i++)p=p*i;returnp;}循环n次，故T(n)=n25Illustration例2Fibonacci数列26Fibonacci数列的前10项为1，1，2，3，5，8，13，21，34，55，…，它可以递归地定义为：边界条件递归方程第n个Fibonacci数可递归地计算如下：fibonacci(intn){if(n=1)return1;elsereturnfibonacci(n-1)+fibonacci(n-2);}110)2()1(11)(nnnnFnFnFT(n)=T(n-1)+T(n-2),T(n)=?271125125151)(nnnF生成函数法！Fibonacci函数也可以找到相应的非递归方式定义：28例3Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：1,20)1),,1((),(2)0,(1),0(2)0,1(mnnmmmnAAmnAnnAmAAAckerman函数无法找到非递归的定义。29Ackerman函数A(n，m)的自变量m的每一个值都定义了一个单变量函数：m=0时，A(n,0)=n+2m=1时，由A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2(n1)，和A(1,1)=2，得A(n,1)=2*nm=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)=。m=3时，类似的可以推出m=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。个nnA2222)3,(1,20)1),,1((),(2)0,(1),0(2)0,1(mnnmmmnAAmnAnnAmAAn230定义单变量的Ackerman函数A(n)为，A(n)=A(n，n)。定义其拟逆函数α(n)为：α(n)=min{k｜A(k)≥n}。即α(n)是使n≤A(k)成立的最小的k值。α(n)在复杂度分析中常遇到。对于通常所见到的正整数n，有α(n)≤4。但在理论上α(n)没有上界，随着n的增加，它以难以想象的慢速度趋向正无穷大。个65536222)4,4(A31例4排列的生成问题设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R\{ri}。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri得到的排列。R的全排列可归纳定义如下：当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。32perm(list[],intk,intm){//产生前缀是list[0:k-1],后缀是list[k:m]的所有排列//perm(list,0,n-1)产生list[0:n-1]的去全排列if(k==m){//单元素排列for(inti=0;i=m;i++)coutlist[i];coutendl;}else{//多元素序列，递归产生排列for(inti=k;i=m;i++){swap(list[k],list[i]);perm(list,k+1,m);swap(list[k],list[i]);}}}1),1(1,1)(nnnTnnT33例.产生123的所有排列层次栈状态(i,k,m)数组输出10，0，232121，1，20，0，23213，2，21，1，20，0，232132122，1，20，0，22313，2，22，1，20，0，223123122，1，20，0，232111，0，231221，1，21，0，23123，2，21，1，21，0，231231222，1，21，0，21323，2，22，1，21，0，213213222，1，21，0，231212，0，231221，1，22，0，2213层次栈状态(i,k,m)数组输出3422，1，22，0，212322，1，22，0，22133，2，21，1，22，0，2213213层次栈状态(i,k,m)数组输出3，2，22，1，22，0，212312312，0，21230栈空12335例5整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。正整数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。36设q(n,m)为n的最大加数n1不大于m的划分个数。则：(1)q(n,1)=1，n≥1;(2)q(n,m)=q(n,n),n≤m;(4)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1≤n-1的划分组成。(5)q(n,m)=q(n-m,m)+q(n,m-1),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1≤m-1的划分组成。(3)q(1,m)=1,m