王晓东《算法设计与分析》课件.ppt

单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,*,*,*,,中国计算机学会“21世纪大学本科计算机专业系列教材”,,算法设计与分析,王晓东 编著,1,,主要内容介绍,第1章 算法引论,,第2章 递归与分治策略,,第3章 动态规划,,第4章 贪心算法,,第5章 回溯法,,第6章 分支限界法,2,,主要内容介绍（续）,第7章 概率算法,,第8章,NP,完全性理论,,第9章 近似算法,,第10章 算法优化策略,3,,第1章 算法引论,1.1 算法与程序,,1.2 表达算法的抽象机制,,1.3 描述算法,,1.4 算法复杂性分析,本章主要知识点：,4,,1.1 算法与程序,输 入：有零个或多个外部量作为算法的输入输 出：算法产生至少一个量作为输出确定性：组成算法的每条指令清晰、无歧义有限性：算法中每条指令的执行次数有限，执行每条指令的时间也有限是算法用某种程序设计语言的具体实现程序可以不满足算法的性质(4)即有限性是满足下述性质的指令序列算法：,程序：,5,,1.从机器语言到高级语言的抽象,1.2 表达算法的抽象机制,高级程序设计语言的主要好处是：,（4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短，程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。

1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作；,（2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计出来的程序可读性好，可维护性强，可靠性高；,（3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而所写出来的程序可植性好、重用率高；,6,,2.抽象数据类型,1.2 表达算法的抽象机制,,抽象数据类型是算法的一个数据模型连同定义在该模型上,,并作为算法构件的一组运算抽象数据类型,带给算法设计的,好处,有,：,,（1）,算法顶层设计与底层实现分离；,,（2）算法设计与数据结构设计隔开，允许数据结构自由选择；,,（3）数据模型和该模型上的运算统一在,ADT,中，便于空间和时间耗费的折衷；,,（4）用抽象数据类型表述的算法具有很好的可维护性；,,（5）算法自然呈现模块化；,,（6）为自顶向下逐步求精和模块化提供有效途径和工具；,,（7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析7,,在本书中，采用,Java,语言,描述算法1.,Java,程序结构,,1.3 描述算法,以下，对,Java,语言,的,若干重要特性,作简要概述。

1）,Java,程序的两种类型：,应用程序和,applet,,,区别：应用程序的主方法为,main,，,其可在命令行中用命令,,语句,java,应用程序名,来执行；,,,applet,的主方法为,init,，,其必须嵌入,HTML,文件，由,,,Web,浏览器或,applet,阅读器来执行2）,包：,java,程序和类可以包,(,packages),的形式组织管理3）,import,语句：,在,java,程序中可用,import,语句加载所需的包例如，,import java.,io,.*;,语句加载,java.,io,包8,,1.3 描述算法,2.,Java,数据类型,数据类型,,基本,数据类型：详见下页表1-1,,非基本,数据类型：如,,Byte, Integer, Boolean, String,等Java,对两种数据类型的不同处理方式：,,对基本,数据类型：,在,声明一个具有基本数据类型的变量时，自,,动建立该数据类型的对象（或称实例）如:,int,k;,对非基本,数据类型：语句,String s;,并不建立具有数据类型,,String,的对象，而是建立一个类型,String,的引用对象，,,数据类型为,String,的对象可用下面的,new,语句建立。

s = new,String,(“Welcome”);,,String,s = new,String,(“Welcome”);,9,,1.3 描述算法,表格1-1,Java,基本数据类型,类型,缺省值,分配空间（,bits）,取值范围,boolean,false,1,[,true,false],byte,0,8,[-128,127],char,\u0000,16,[\u0000,\,uFFFF,],double,0.0,64,±4.9*10,-324,~ ±1.8*10,308,float,0.0,32,±1.4*10,-45,~ ±3.4*10,38,int,0,32,[-2147483648,2147483647],long,0,64,±9.2*10,17,short,0,16,[-32768,32767],10,,1.3 描述算法,3.方法,在,Java,中，执行特定任务的,函数或过程,统称为方法,(,methods),例如，,java,的,Math,类,给出的常见数学计算的方法如下表所示,：,方法,功能,方法,功能,abs(x),x,的绝对值,max(x,y),x,和,y,中较大者,ceil(x),不小于,x,的最小整数,min(x,y),x,和,y,中较小者,cos,(x),x,的余弦,pow,(x,y),x,y,exp(x),e,x,sin(x),x,的正弦,floor(x),不大于,x,的最大整数,sqrt,(x),x,的平方根,log(x),x,的自然对数,tan(x),x,的正切,11,,1.3 描述算法,3.方法,,计算表达式 值的自定义方法,ab,描述如下：,,,public static,int,ab,(,int,a,,int,b),,{,,return,(a+b+Math.abs(a-b))/2;,,},,（1）方法参数：,Java,中所有方法的参数均为值参数。

上述方法,ab,中，,a,和,b,是形式参数，在调用方法时通过实际参数赋值2）方法重载：,Java,允许方法重载，即允许定义有不同签名的同名方法上述方法,ab,可重载为：,,,public static double,ab,(double a, double b),,{,,return,(a+b+Math.abs(a-b))/2.0;,,},,12,,1.3 描述算法,4.异常,Java,的异常提供了一种处理错误的方法当程序发现一个错误，就引发一个异常，以便在合适地方捕获异常并进行处理通常用,try,块来定义异常处理每个异常处理由一个,catch,语句组成public static void,main,(String [],args,),,{,,try,{ f ( ); },,,catch,(exception1),,{,异常处理,; },,,,catch,(exception2),,{,异常处理,; },,,…,,,finally,,{ finally,块,; },,},,13,,1.3 描述算法,,5.,Java,的类,(4),访问修饰,公有(,public),私有,(,private),保护,(,protected),Java,的类一般由,4,个部分组成：,(1),类名,(2),数据成员,(3),方法,14,,1.3 描述算法,6.通用方法,,,下面的方法,swap,用于交换一维整型数组,a,的位置,i,和位置,j,处的值。

public static void,swap,(,int,[] a,,int,i,,int,j),,{,,,int,temp = a[i];,,a[i] = a[j];,,a[j] = temp;,,},,public static void,swap,(object [] a,,int,i,,int,j),,{,,object temp = a[i];,,a[i] = a[j];,,a[j] = temp;,,},,该方法只适用于,,整型数组,该方法具有通用性，适用于,Object,类型及其所有子类,以上方法修改如下：,15,,1.3 描述算法,6.通用方法,,（1）,Computable,界面,,public static,Computable,sum,(Computable [] a,,int,n),,{,,if (a.length == 0) return null;,,Computable sum = (Computable) a[0].zero();,,for (,int,i = 0; i < n; i++),,sum.increment(a[i]);,,return sum;,,},利用此界面使,,方法,sum,通用化,,16,,1.3 描述算法,6.通用方法,,（2）,java.lang.Comparable,界面,Java,的,Comparable,界面中惟一的方法头,compareTo,用于比较,,2个元素的大小。

例如,java.lang.Comparable.x.,compareTo,(y),,返回,x-y,的符号，当,xy,时返,,回正数3）,Operable,,界面,有些通用方法同时需要,Computable,界面和,Comparable,界面,,的支持为此可定义,Operable,界面如下:,public interface,Operable,extends Computable, Comparable,,{},,（4）自定义包装类,由于,Java,的包装类如,Integer,等已定义为,final,型，因此无法,,定义其子类，作进一步扩充为了需要可自定义包装类17,,1.3 描述算法,,7.垃圾收集,,,,,8.,递归,,Java,的,new,运算用于分配所需的内存空间例如，,int,[] a = new,int,[500000];,分配2000000字节空间,,给整型数组,a频繁用,new,分配空间可能会耗尽内存Java,的,垃,,圾收集器,会适时扫描内存，回收不用的空间（垃圾）给,new,重新,,分配Java,允许方法调用其自身这类方法称为递归方法。

public static,int,,sum,(,int,[] a,,int,n),,{,,if (n==0) return 0;,,else return a[n-1]+sum(a,n-1);,,},,计算一维整型数组前,n,个元素之和的递归方法,,18,,1.4 算法复杂性分析,,算法复杂性是算法运行所需要的计算机资源的量，,,需要时间资源的量称为,时间复杂性,，需要的空间资源的,,量称为,空间复杂性,这个量应该只依赖于算法要解的问,,题的规模、算法的输入和算法本身的函数如果分别用,,N、I,和,A,表示算法要解问题的规模、算法的输入和算法,,本身，而且用,C,表示复杂性，那么，应该有,C=F(N,I,A)一般把时间复杂性和空间复杂性分开，并分别用,T,和,S,来,,表示，则有：,T=T(N,I),和,S=S(N,I),,通常，让,A,隐含在复杂性函数名当中）,,19,,1.4 算法复杂性分析,最坏情况下的时间复杂性：,最好情况下的时间复杂性：,平均情况下的时间复杂性：,其中,D,N,是规模为,N,的合法输入的集合；,I,*,是,D,N,中使,T(N, I,*,),,达到,T,max,(N),的合法输入； 是中使,T(N, ),达到,T,min,(N),的合法,,输入；而,P(I),是在算法的应用中出现输入,I,的概率。

20,,1.4 算法复杂性分析,算法复杂性在渐近意义下的阶：,渐近意义下的记号：,O、,Ω,、,θ,、o,,,设,f(N),和,g(N),是定义在正数集上的正函数O,的定义,：如果存在正的常数,C,和自然数,N,0,，,使得当,N,,N,0,时有,f(N),C,g(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)21,,1.4 算法复杂性分析,Ω,的定义,：如果存在正的常数,C,和自然数,N,0,，,使得当,N,,N,0,时,,有,f(N),C,g(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，,都存在正整数,N,0,，,使得,,当,N,,N0,时有,f(N),/C,g(N),,ε,,则称函数,f(N),当,N,充分大时的阶比,,g(N),低，记为,f(N)=o(g(N)),例如，4,NlogN,+7=o(3N,2,+4NlogN+7)22,,第,2,章 递归与分治策略,23,,将要求解的较大规模的问题分割成,k,个更小规模的子问题算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,,,,对这,k,个子问题分别求解如果子问题的规模仍然不够小，则再划分为,k,个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止24,,算法总体思想,对这,k,个子问题分别求解如果子问题的规模仍然不够小，则再划分为,k,个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),,,,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。

25,,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),26,,算法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解n,T(n),=,n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),n/2,T(n/4),T(n/4),T(n/4),T(n/4),,,,,,,,分治法的设计思想是，将一个难以直接解决的大问题，,,分割成一些规模较小的相同问题，以便各个击破，,,分而治之凡治众如治寡，分数是也孙子兵法,27,,2.1,递归的概念,直接或间接地调用自身的算法称为,递归算法,用函数自身给出定义的函数称为,递归函数,。

由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解这自然导致递归过程的产生分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法下面来看几个实例28,,2.1,递归的概念,例,1,阶乘函数,,阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果29,,2.1,递归的概念,例,2 Fibonacci,数列,,无穷数列1，1，2，3，5，8，13，21，34，55，,…,，,被,称为Fibonacci数列它可以递归地定义为：,,边界条件,递归方程,第,n,个,Fibonacci,数可递归地计算如下：,,public static,int,fibonacci,(,int,n),,{,,,if,(n <= 1),return,1;,,,return,,fibonacci,(n-1)+,fibonacci,(n-2);,,},30,,,,31,,2.1,递归的概念,例,3,Ackerman,函数,,当一个函数及它的一个变量是由函数自身定义时，称这个函数是,双递归函数,。

Ackerman,函数,A(n,，,m),定义如下：,,32,,2.1,递归的概念,例,3,Ackerman,函数,,前,2,例中的函数都可以找到相应的非递归方式定义：,但本例中的,Ackerman,函数却无法找到非递归的定义33,,2.1,递归的概念,例,3,Ackerman函数,,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,，和,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)= 2^n,M=3,时，类似的可以推出,,M=4,时，,A(n,4),的增长速度非常快，以至于没有适当的数学式子来表示这一函数34,,2.1,递归的概念,例,3,Ackerman函数,,定义单变量的,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,的增加，它以难以想象的慢速度趋向正无穷大35,,2.1,递归的概念,例,4,排列问题,,设计一个递归算法生成,n,个元素,{r,1,,r,2,,…,,r,n,},的全排列设,R=,{r,1,,r,2,,…,,r,n,},是要进行排列的,n,个元素，,R,i,=R-{,r,i,},集合,X,中元素的全排列记为,perm(X),r,i,)perm(X),表示在全排列,perm(X),的每一个排列前加上前缀得到的排列R,的全排列可归纳定义如下：,,当,n=1,时，,perm(R)=(r),，,其中,r,是集合,R,中唯一的元素；,,当,n>1,时，,perm(R),由,(,r,1,)perm(R,1,),，,(r,2,)perm(R,2,),，,…,，,(,r,n,)perm(,R,n,),构成36,,2.1,递归的概念,例,5,整数划分问题,,将正整数,n,表示成一系列正整数之和：,n=n,1,+n,2,+…+,n,k,，,,其中,n,1,≥n,2,≥…≥n,k,≥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,37,,(2),q(n,m)=q(n,n),m,,n;,,最大加数,n,1,实际上不能大于,n,因此，,q(1,m)=1,1),q(n,1)=1,n,,1;,,当最大加数,n,1,不大于,1,时，任何正整数,n,只有一种划分形式，,,即,,,,,,(4),q(n,m)=q(n,m-1)+q(n-m,m),n>m>1;,,正整数,n,的最大加数,n,1,不大于,m,的划分由,n,1,=m,的划分和,,n,1,≤n-1,的划分组成3),q(n,n)=1+q(n,n-1);,,正整数,n,的划分由,n,1,=n,的划分和,n,1,≤n-1,的划分组成2.1,递归的概念,例,5,整数划分问题,,前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。

在本例中，如果设,p(n),为正整数,n,的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数,n,1,不大于,m,的划分个数记作,q(n,m),可以建立,q(n,m),的如下递归关系38,,2.1,递归的概念,例,5,整数划分问题,,前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解在本例中，如果设,p(n),为正整数,n,的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数,n,1,不大于,m,的划分个数记作,q(n,m),可以建立,q(n,m),的如下递归关系正整数,n,的划分数,p(n)=q(n,n),39,,,,40,,2.1,递归的概念,例,6 Hanoi,塔问题,,设,a,b,c,是,3,个塔座开始时，在塔座,a,上有一叠共,n,个圆盘，这些圆盘自下而上，由大到小地叠在一起各圆盘从小到大编号为,1,2,…,n,,现要求将塔座,a,上的这一叠圆盘移到塔座,b,上，并仍按同样顺序叠置在移动圆盘时应遵守以下移动规则：,,规则,1,：每次只能移动,1,个圆盘；,,规则,2,：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；,,规则,3,：在满足移动规则,1,和,2,的前提下，可将圆盘移至,a,b,c,中任一塔座上。

41,,在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题当,n=1,时，问题比较简单此时，只要将编号为,1,的圆盘从塔座,a,直接移至塔座,b,上即可当,n,＞,1,时，需要利用塔座,c,作为辅助塔座此时若能设法将,n-1,个较小的圆盘依照移动规则从塔座,a,移至塔座,c,，,然后，将剩下的最大圆盘从塔座,a,移至塔座,b,，,最后，再设法将,n-1,个较小的圆盘依照移动规则从塔座,c,移至塔座,b,由此可见，,n,个圆盘的移动问题可分为,2,次,n-1,个圆盘的移动问题，这又可以递归地用上述方法来做由此可以设计出解,Hanoi,塔问题的递归算法如下2.1,递归的概念,例,6,Hanoi,塔问题,,,,,,,public static void,,hanoi,(,int,n,,int,a,,int,b,,int,c),,{,,,if,(n > 0),,{,,,hanoi,(n-1, a, c, b);,,,move,(a,b);,,,hanoi,(n-1, c, b, a);,,},,},,思考题：如果塔的个数变为,a,b,c,d,四个，现要将,n,个圆盘从,a,全部移动到,d,，,移动规则不变，求移动步数最小的方案。

42,,递归小结,优点：,结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便缺点：,递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多43,,递归小结,解决方法：,在递归算法中消除递归调用，使其转化为非递归算法1.,采用一个用户定义的栈来模拟系统的递归调用工作栈该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显2.,用递推来实现递归函数3.,通过,Cooper,变换、,反演变换能,将一些递归转化为尾递归，从而迭代求出结果后两种方法在时空复杂度上均有较大改善，但其适用范围有限44,,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：,,该问题的规模缩小到一定的程度就可以容易地解决；,,该问题可以分解为若干个规模较小的相同问题，即该问题具有,最优子结构性质,,利用该问题分解出的子问题的解可以合并为该问题的解；,,该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑,贪心算法,或,动态规划,。

这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用,动态规划,较好45,,分治法的基本步骤,divide-and-conquer,(P),,{,,,if,( | P | <= n0),adhoc,(P,); //,解决小规模的问题,,,divide,P into smaller,subinstances,P1,P2,...,,Pk,；,//,分解问题,,,for,(i=1,i<=k,i++),,,yi,=,divide-and-conquer,(Pi); //,递归的解各子问题,,,return,merge(y1,...,,yk,); //,将各子问题的解合并为原问题的解,,,},,,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同即将一个问题分成大小相等的,k,个子问题的处理方法是行之有效的这种使子问题规模大致相等的做法是出自一种,平衡,(balancing),子问题,的思想，它几乎总是比子问题规模不等的做法要好46,,分治法的复杂性分析,一个分治法将规模为,n,的问题分成,k,个规模为,n,／,m,的子问题去解。

设分解阀值,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),是单调上升的，从而当,m,i,≤na[i],，,同理我们只要在,a[mid],的后面查找,x,即可。

无论是在前面还是后面查找,x,，,其方法都和在,a,中查找,x,一样，只不过是查找的规模缩小了这就说明了此问题满足分治法的第二个和第三个适用条件分析：,很显然此问题分解出的子问题相互独立，即在,a[i],的前面或后面查找,x,是独立的子问题，因此满足分治法的第四个适用条件给定已按升序排好序的,n,个元素,a[0:n-1],，,现要在这,n,个元素中找出一特定元素,x,分析：,,该问题的规模缩小到一定的程度就可以容易地解决；,,该问题可以分解为若干个规模较小的相同问题,;,,分解出的子问题的解可以合并为原问题的解；,,分解出的各个子问题是相互独立的48,,二分搜索技术,给定已按升序排好序的,n,个元素,a[0:n-1],，,现要在这,n,个元素中找出一特定元素,x,据此容易设计出,二分搜索算法,：,,public static,int,binarySearch,(,int,[] a,,int,x,,int,n),,{,,//,在,a[0] <= a[1] <= ... <= a[n-1],中搜索,x,,//,找到,x,时返回其在数组中的位置，否则返回,-1,,,int,left = 0;,int,right = n - 1;,,,while,(left <= right) {,,int,middle = (left + right)/2;,,,if,(x == a[middle]),return,middle;,,,if,(x > a[middle]) left = middle + 1;,,,else,right = middle - 1;,,},,,return,-1; //,未找到,x,,},算法复杂度分析：,,每执行一次算法的,while,循环， 待搜索数组的大小减少一半。

因此，在最坏情况下，,while,循环被执行了,O(,logn,),次循环体内运算需要,O(1),时间，因此整个算法在最坏情况下的计算时间复杂性为,O(,logn,),思考题：,给定a，用二分法设计出求a,n,的算法49,,大整数的乘法,,请设计一个有效的算法，可以进行两个,n,位大整数的乘法运算,小学的方法：,O(n,2,),,效率太低,,分治法,:,a,b,c,d,复杂度分析,,,,T(n)=O(n,2,),,没有改进,,X =,,Y =,,,X =,a,2,n/2,+,b,Y =,c,2,n/2,+,d,,,XY =,ac,2,n,+ (,ad,+,bc,) 2,n/2,+,,bd,,50,,大整数的乘法,请设计一个有效的算法，可以进行两个,n,位大整数的乘法运算,小学的方法：,O(n,2,),,效率太低,,分治法,:,XY =,ac,2,n,+ (,ad,+,bc,) 2,n/2,+,bd,,,,为了降低时间复杂度，必须减少乘法的次数XY =,ac,2,n,+ ((,a,-,c,)(,b,-,d,)+,ac,+,bd,) 2,n/2,+,,bd,,XY =,ac,2,n,+ ((,a,+,c,)(,b,+,d,)-,ac,-,bd,) 2,n/2,+,,bd,复杂度分析,,,,T(n)=O(n,log3,) =O(n,1.59,),,较大的改进,,细节问题,：两个,XY,的复杂度都是,O(n,log3,),，,但考虑到,a+c,b+d,可能得到,m+1,位的结果，使问题的规模变大，故不选择第,2,种方案。

51,,大整数的乘法,请设计一个有效的算法，可以进行两个,n,位大整数的乘法运算,小学的方法：,O(n,2,),,效率太低,,分治法,:,O(n,1.59,),,较大的改进,,更快的方法,??,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法最终的，这个思想导致了,快速傅利叶变换,(,Fast Fourier Transform),的产生该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在,O(,nlogn,),时间内解决是否能找到线性时间的算法？？？目前为止还没有结果52,,Strassen,矩阵乘法,A,和,B,的乘积矩阵,C,中的元素,C[i,j],定义为,:,,,若依此,定义,来,计算,A和B的,乘积矩阵,C，则每,计算,C的,一个元素,C[i][j]，,需要,做n次,乘法,和n-1次,加法,因此,，算出,矩阵,C的 个,元素,所需的,计算时间,为,O(n,3,),传统方法,：,O(n,3,),53,,Strassen,矩阵乘法,使用,与上例,类似,的技术，将,矩阵,A，B和C中每一,矩阵,都分块成4个,大小,相等的子,矩阵,由此可将方程C=AB,重写,为：,传统方法,：,O(n,3,),,分治法,:,由此可得：,复杂度分析,,,,T(n)=O(n,3,),,没有改进,,54,,Strassen,矩阵乘法,传统方法,：,O(n,3,),,分治法,:,为了降低时间复杂度，必须减少乘法的次数。

复杂度分析,,,,T(n)=O(n,log7,) =O(n,2.81,),,较大的改进,,55,,Strassen,矩阵乘法,传统方法,：,O(n,3,),,分治法,:,O(n,2.81,),,更快的方法,??,Hopcroft,和,Kerr,已经证明,(1971),，计算,2,个２,×,２矩阵的乘积，,7,次乘法是必要的因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算,2×2,矩阵的,7,次乘法这样的方法了或许应当研究３,×,３或５,×,５矩阵的更好算法在,Strassen,之后又有许多算法改进了矩阵乘法的计算时间复杂性目前最好的计算时间上界是,O(n,2.376,),,,是否能找到,O(n,2,),的算法？？？目前为止还没有结果56,,棋盘覆盖,在一个,2,k,×,2,k,,个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘在棋盘覆盖问题中，要用图示的,4,种不同形态的,L,型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何,2,个,L,型骨牌不得重叠覆盖57,,棋盘,覆盖,当,k>0,时，将,2,k,×,2,k,棋盘分割为,4,个,2,k-1,×,2,k-1,,子棋盘,(,a),所示。

特殊方格必位于,4,个较小子棋盘之一中，其余,3,个子棋盘中无特殊方格为了将这,3,个无特殊方格的子棋盘转化为特殊棋盘，可以用一个,L,型骨牌覆盖这,3,个较小棋盘的会合处，如,,(,b),所示，从而将原问题转化为,4,个较小规模的棋盘覆盖问题递归地使用这种分割，直至棋盘简化为棋盘,1,×,1,58,,棋盘,覆盖,,public void,,chessBoard,(,int tr,,,int tc,,,int dr,,,int,dc,,int,size),,{,,,if,(size == 1),return,;,,int,t = tile++, // L,型骨牌号,,,s = size/2; //,分割棋盘,,,//,覆盖左上角子棋盘,,,if,(,dr,<,tr,+ s && dc <,tc,+ s),,//,特殊方格在此棋盘中,,,chessBoard,(,tr,,,tc,,,dr,, dc, s);,,,else,{//,此棋盘中无特殊方格,,,//,用,t,号,L,型骨牌覆盖右下角,,,board[,tr,+ s - 1][,tc,+ s - 1] = t;,,//,覆盖其余方格,,,chessBoard,(,tr,,,tc,,,tr,+s-1,,tc,+s-1, s);},,//,覆盖右上角子棋盘,,,if,(,dr,<,tr,+ s && dc >=,tc,+ s),,//,特殊方格在此棋盘中,,,chessBoard,(,tr,,,tc,+s,,dr,, dc, s);,,,else,{//,此棋盘中无特殊方格,,,//,用,t,号,L,型骨牌覆盖左下角,,,,board[,tr,+ s - 1][,tc,+ s] = t;,,//,覆盖其余方格,,,chessBoard,(,tr,,,tc,+s,,tr,+s-1,,tc,+s, s);},,//,覆盖左下角子棋盘,,,if,(,dr,>=,tr,+ s && dc <,tc,+ s),,//,特殊方格在此棋盘中,,,chessBoard,(,tr,+s,,tc,,,dr,, dc, s);,,,else,{//,用,t,号,L,型骨牌覆盖右上角,,,board[,tr,+ s][,tc,+ s - 1] = t;,,//,覆盖其余方格,,,chessBoard,(,tr,+s,,tc,,,tr,+s,,tc,+s-1, s);},,//,覆盖右下角子棋盘,,,if,(,dr,>=,tr,+ s && dc >=,tc,+ s),,//,特殊方格在此棋盘中,,,chessBoard,(,tr,+s,,tc,+s,,dr,, dc, s);,,,else,{//,用,t,号,L,型骨牌覆盖左上角,,,board[,tr,+ s][,tc,+ s] = t;,,//,覆盖其余方格,,,chessBoard,(,tr,+s,,tc,+s,,tr,+s,,tc,+s, s);},,},复杂度分析,,,,T(n)=O(4,k,),渐进意义下的最优算法,59,,合并排序,,基本思想：,将待排序元素分成大小大致相同的,2,个子集合，分别对,2,个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。

public static void,,mergeSort,(Comparable a[],,int,left,,int,right),,{,,,if,(left

62,,快速排序,在快速排序中，记录的比较和交换是从两端向中间,,进行的，关键字较大的记录一次就能交换到后面单,,元，关键字较小的记录一次就能交换到前面单元，,,记录每次移动的距离较大，因而总的比较和移动次,,数较少private static void,,qSort,(,int,p,,int,r),,{,,,if,(p=,x,的元素交换到左边区域,,,//,将,<=,x,的元素交换到右边区域,,,while,(,true,) {,,,while,(a[++i].,compareTo,(x) < 0);,,,while,(a[--j].,compareTo,(x) > 0);,,,if,(i >= j),break,;,,MyMath,.,swap,(a, i, j);,,},,a[p] = a[j];,,a[j] = x;,,,return,j;,,},初始序列,{,6,,,7, 5, 2, 5, 8},j--;,{5,,,7, 5, 2,,6,, 8},i++;,{5,,,6,, 5, 2, 7, 8},j--;,{5,,,2, 5,,6,, 7, 8},i++;,完成,快速排序具有,不稳定性,。

{,6,,,7, 5, 2, 5, 8},{5,,,2, 5},6,{7, 8},64,,private static,int,randomizedPartition,(,int,p,,int,r),,{,,int,i =,random,(p,r);,,MyMath,.,swap,(a, i, p);,,,return,,partition,(p, r);,,},快速排序,快速排序算法的性能取决于划分的对称性通过修改算法,partition,，,可以设计出采用随机选择策略的快速排序算法在快速排序算法的每一步中，当数组还没有被划分时，可以在,a[p:r],中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的最坏时间复杂度：,O(n,2,),,平均时间复杂度：,O(,nlogn,),,辅助空间：,O(n),或,O(,logn,),,稳定性：不稳定,65,,线性时间选择,给定线性序集中,n,个元素和一个整数,k,，,1≤k≤n,，,要求找出这,n,个元素中第,k,小的元素,private static Comparable,,randomizedSelect,(,int,p,,int,r,,int,k),,{,,,if,(p==r),return,a[p];,,int,i=,randomizedpartition,(p,r),,,j=i-p+1;,,,if,(k<=j),return,,randomizedSelect,(p,i,k);,,,else,,return,,randomizedSelect,(i+1,r,k-j);,,},在最坏情况下，算法,randomizedSelect,需要,O(n,2,),计算时间,,但可以证明，算法,randomizedSelect,可以在,O(n),平均时间内找出,n,个输入元素中的第,k,小元素。

66,,线性时间选择,如果能性时间内找到一个划分基准，使得按这个基准所划分出的,2,个子数组的长度都至少为原数组长度的,ε,倍,(0<,ε<1,是某个正常数,),，那么就可以,在最坏情况下,用,O(n),时间完成选择任务例如，若,ε=9/10,，,算法递归调用所产生的子数组的长度至少缩短,1/10,所以，在最坏情况下，算法所需的计算时间,T(n),满足递归式,T(n)≤T(9n/10)+O(n),由此可得,T(n)=O(n),67,,将,n,个输入元素划分成,n/5,个组，每组,5,个元素，只可能有一个组不是,5,个元素用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共,n/5,个递归调用,select,来找出这,n/5,,个元素的中位数如果,,n/5,,是偶数，就找它的,2,个中位数中较大的一个以这个元素作为划分基准线性时间选择,设所有元素互不相同在这种情况下，找出的基准,x,至少比,3(,n-5)/10,个元素大，因为在每一组中有,2,个元素小于本组的中位数，而,n/5,个中位数中又有,(,n-5)/10,个小于基准,x,同理，基准,x,也至少比,3(,n-5)/10,个元素小。

而当,n≥75,时，,3(,n-5)/10≥n/4,所以按此基准划分所得的,2,个子数组的长度都至少缩短,1/4,68,,private static Comparable,select,(,int,p,,int,r,,int,k),,{,,,if,(r-p<5) {,,//,用某个简单排序算法对数组,a[p:r],排序,;,,,bubbleSort,(p,r);,,,return,a[p+k-1];,,},,//,将,a[p+5*i],至,a[p+5*i+4],的第,3,小元素,,,//,与,a[p+i],交换位置,;,,//,找中位数的中位数，,r-p-4,即上面所说的,n-5,,,for,(,int,i = 0; i<=(r-p-4)/5; i++ ),,{,,int,s=p+5*i,,,t=s+4;,,,for,(,int,j=0;j<3;j++),bubble,(s,t-j);,,MyMath,.,swap,(a, p+i, s+2);,,},,Comparable x =,select,(p, p+(r-p-4)/5, (r-p+6)/10);,,int,i=,partition,(p,r,x),,,j=i-p+1;,,,if,(k<=j),return,,select,(p,i,k);,,,else return select,(i+1,r,k-j);,,},复杂度分析,,,,T(n)=,O(n),上述算法将每一组的大小定为,5,，并选取,75,作为是否作递归调用的分界点。

这,2,点保证了,T(n),的递归式中,2,个自变量之和,n/5+3n/4=19n/20=,ε,n,，,0<,ε,<1,这是使,T(n)=O(n),的关键之处当然，除了,5,和,75,之外，还有其他选择69,,最接近点对问题,给定平面上,n,个点的集合,S,，,找其中的一对点，使得在,n,个点组成的所有点对中，该点对间的距离最小为了使问题易于理解和分析，先来考虑,一维,的情形此时，,S,中的,n,个点退化为,x,轴上的,n,个实数,x1,x2,…,,xn,最接近点对即为这,n,个实数中相差最小的,2,个实数假设我们用,x,轴上某个点,m,将,S,划分为,2,个子集,S1,和,S2,，,基于,平衡子问题,的思想，用S中各点坐标的中位数来作分割点递归地在,S1,和,S2,上找出其最接近点对,{,p1,p2},和,{,q1,q2},，,并设,d=min{|p1-p2|,|q1-q2|},，,S,中的最接近点对或者是,{,p1,p2},，,或者是,{,q1,q2},，,或者是某个,{,p3,q3},，,其中,p3∈S1,且,q3∈S2,能否性时间内找到,p3,q3,？,70,,最接近点对问题,如果,S,的最接近点对是,{,p3,q3},，,即,|,p3-q3|

由于在,S1,中，每个长度为,d,的半闭区间至多包含一个点（否则必有两点距离小于,d,），,并且,m,是,S1,和,S2,的分割点，因此,(,m-d,m],中至多包含,S,中的一个点由图可以看出，,如果,(,m-d,m],中有,S,中的点，则此点就是,S1,中最大点因此，我们用线性时间就能找到区间,(,m-d,m],和,(,m,m+d],中所有点，即,p3,和,q3,。