1、自动化系算法设计与分析自动化系算法设计与分析 配套全册教学课件配套全册教学课件 算法设计与分析 西安交通大学西安交通大学 计算机系计算机系 2021-7-18算法设计与分析课件3 第1章 算法引论 n1.1 算法与程序 n1.2 表达算法的抽象机制 n1.3 描述算法 n1.4 算法复杂性分析 本章主要知识点： 2021-7-18算法设计与分析课件4 1.1 算法与程序 n输 入：有零个或多个外部量作为算法的输入。 n输 出：算法产生至少一个量作为输出。 n确定性：组成算法的每条指令清晰、无歧义。 n有限性：算法中每条指令的执行次数有限，执行 每条指令的时间也有限。 算法：算法：是满足下述性质
2、的指令序列。 2021-7-18算法设计与分析课件5 1.1 算法与程序 程序：程序：是算法用某种程序设计语言的具体实现。 程序可以不满足算法的性质(4)即有限性。 l 例如操作系统，是一个在无限循环中执行的 程序，因而不是一个算法。 l 操作系统的各种任务可看成是单独的问题， 每一个问题由操作系统中的一个子程序通过 特定的算法来实现。该子程序得到输出结果 后便终止。 2021-7-18算法设计与分析课件6 1.1 算法与程序 n算法的研究可以分成四个不同的领域：算法的研究可以分成四个不同的领域： 1）怎样设计算法： 算法设计的策略，技巧 2）怎样验证算法： 验证算法可以正确运行。 程序验证；
3、 算法证明 3）怎样分析算法： 算法分析，分析算法的性能 （时间/空间） 4）怎样测试算法： 包括调试、评测 本课程主要集中于算法的设计与分析。 2021-7-18算法设计与分析课件7 1.从机器语言到高级语言的抽象 1.2 表达算法的抽象机制 高级程序设计语言的主要好处是： （4）把繁杂琐碎的事务交给编译程序，所以自动化程度高，开发周期短， 程序员可以集中时间和精力从事更重要的创造性劳动，提高程序质量。 （1）高级语言更接近算法语言，易学、易掌握，一般工程技术人员只需 要几周时间的培训就可以胜任程序员的工作； （2）高级语言为程序员提供了结构化程序设计的环境和工具，使得设计 出来的程序可读性
4、好，可维护性强，可靠性高； （3）高级语言不依赖于机器语言，与具体的计算机硬件关系不大，因而 所写出来的程序可植性好、重用率高； 2021-7-18算法设计与分析课件8 2.抽象数据类型 1.2 表达算法的抽象机制 抽象数据类型是算法的一个数据模型连同定义在该模型上 并作为算法构件的一组运算。 抽象数据类型带给算法设计的好处有： （1）算法顶层设计与底层实现分离； （2）算法设计与数据结构设计隔开，允许数据结构自由选择； （3）数据模型和该模型上的运算统一在ADT中，便于空间和时间耗费的折衷； （4）用抽象数据类型表述的算法具有很好的可维护性； （5）算法自然呈现模块化； （6）为自顶向下逐步
5、求精和模块化提供有效途径和工具； （7）算法结构清晰，层次分明，便于算法正确性的证明和复杂性的分析。 2021-7-18算法设计与分析课件9 在本书中，采用Java语言描述算法。 1.1.JavaJava程序结构程序结构 1.3 描述算法 以下，对JavaJava语言的若干重要特性作简要概述。 （1）Java程序的两种类型：应用程序和appletapplet 区别：应用程序的主方法为main，其可在命令行中用命令 语句 java 应用程序名 来执行； applet的主方法为init，其必须嵌入HTML文件，由 Web浏览器或applet阅读器来执行。 （2）包：java程序和类可以包(pack
6、ages)的形式组织管理。 （3）import语句：在java程序中可用import语句加载所需的包。 例如，import java.io.*;语句加载java.io包。 2021-7-18算法设计与分析课件10 1.3 描述算法 2.2.JavaJava数据类型数据类型 数据类型 基本数据类型：详见下页表1-1 非基本数据类型：如 Byte, Integer, Boolean, String等。 Java对两种数据类型的不同处理方式： 对基本数据类型：在声明一个具有基本数据类型的变量时，自 动建立该数据类型的对象（或称实例）。如:int k; 对非基本数据类型：语句 String s; 并不
7、建立具有数据类型 String的对象，而是建立一个类型String的引用对象， 数据类型为String的对象可用下面的new语句建立。 s = new StringString(“Welcome”); StringString s = new StringString(“Welcome”); 2021-7-18算法设计与分析课件11 1.3 描述算法 表格表格1-1 1-1 JavaJava基本数据类型基本数据类型 类型缺省值分配空间（bits）取值范围 booleanfalse1true,false byte08-128,127 charu000016u0000,uFFFF double0.
8、0644.9*10-324 1.8*10308 float0.0321.4*10-45 3.4*1038 int032-2147483648,2147483647 long0649.2*1017 short016-32768,32767 2021-7-18算法设计与分析课件12 1.3 描述算法 3.3.方法方法 在Java中，执行特定任务的函数或过程统称为方法(methods) 。 例如，java的MathMath类类给出的常见数学计算的方法如下表所示： 方法方法功能功能方法方法功能功能 abs(x)x的绝对值max(x,y)x和y中较大者 ceil(x)不小于x的最小整数min(x,y)x
9、和y中较小者 cos(x)x的余弦pow(x,y)xy exp(x)exsin(x)x的正弦 floor(x)不大于x的最大整数sqrt(x)x的平方根 log(x)x的自然对数tan(x)x的正切 2021-7-18算法设计与分析课件13 1.3 描述算法 3.3.方法方法 2 baba 计算表达式 值的自定义方法ab描述如下： public static int ab(int a, int b) return (a+b+Math.abs(a-b)/2; （1）方法参数：Java中所有方法的参数均为值参数。上述方法ab中， a和b是形式参数，在调用方法时通过实际参数赋值。 （2）方法重载：J
10、ava允许方法重载，即允许定义有不同签名的同名方法。 上述方法ab可重载为： public static double ab(double a, double b) return (a+b+Math.abs(a-b)/2.0; 2021-7-18算法设计与分析课件14 1.3 描述算法 4.4.异常异常 Java的异常提供了一种处理错误的方法。当程序发现一个 错误，就引发一个异常，以便在合适地方捕获异常并进行处理。 通常用trytry块来定义异常处理。每个异常处理由一个catchcatch 语句组成。 public static void main(String args) try f ( )
11、; catch (exception1) 异常处理; catch (exception2) 异常处理; finally finally块; 2021-7-18算法设计与分析课件15 1.3 描述算法 5.5.JavaJava的类的类 (4)访问修饰访问修饰 公有(public) 私有(private) 保护(protected) Java的类一般由4个部分组成： (1)类名类名 (2)数据成员数据成员 (3)方法方法 2021-7-18算法设计与分析课件16 1.3 描述算法 6.6.通用方法通用方法 下面的方法swapswap用于交换一维整型数组a的位置i和位置j处的值。 public st
12、atic void swap(int a, int i, int j) int temp = ai; ai = aj; aj = temp; public static void swap(object a, int i, int j) object temp = ai; ai = aj; aj = temp; 该方法只适用于该方法只适用于 整型数组整型数组 该方法具有通用性，适用该方法具有通用性，适用 于于ObjectObject类型及其所有子类型及其所有子 类类 以上方法修改如下：以上方法修改如下： 2021-7-18算法设计与分析课件17 1.3 描述算法 6.6.通用方法通用方法 （1
13、 1）ComputableComputable界面界面 public static Computable sum(Computable a, int n) if (a.length = 0) return null; Computable sum = (Computable) a0.zero(); for (int i = 0; i n; i+) sum.increment(ai); return sum; 利用此界面使利用此界面使 方法方法sumsum通用化通用化 2021-7-18算法设计与分析课件18 1.3 描述算法 6.6.通用方法通用方法 （2 2）java.lang.Compar
14、able java.lang.Comparable 界面界面 Java的Comparable 界面中惟一的方法头compareTo用于比较 2个元素的大小。例如java.lang.CpareTo(y) 返回x-y的符号，当xy时返 回正数。 （3 3）OperableOperable 界面界面 有些通用方法同时需要Computable界面和Comparable 界面 的支持。为此可定义Operable界面如下: public interface Operable extends Computable, Comparable （4 4）自定义包装类）自定义包装类 由于Java的包装类如Integ
15、er等已定义为final型，因此无法 定义其子类，作进一步扩充。为了需要可自定义包装类。 2021-7-18算法设计与分析课件19 1.3 描述算法 7.7.垃圾收集垃圾收集 8.8.递归递归 Java的newnew运算用于分配所需的内存空间。 例如， int a = new int500000; 分配2000000字节空间 给整型数组a。频繁用new分配空间可能会耗尽内存。Java的垃垃 圾收集器圾收集器会适时扫描内存，回收不用的空间（垃圾）给new重新 分配。 Java允许方法调用其自身。这类方法称为递归方法。 public static int sum(int a, int n) if
16、(n=0) return 0; else return an-1+sum(a,n-1); 计算一维整型数组前计算一维整型数组前n n个个 元素之和的递归方法元素之和的递归方法 2021-7-18算法设计与分析课件20 1.4 算法复杂性分析 算法复杂性是算法运行所需要的计算机资源的 量，需要时间资源的量称为时间复杂性时间复杂性，需要的空 间资源的量称为空间复杂性空间复杂性。这个量应该只依赖于 算法要解的问题的规模、算法的输入和算法本身的 函数。如果分别用N、I和A表示算法要解问题的规模、 算法的输入和算法本身，而且用C表示复杂性，那么， 应该有C=F(N,I,A)。 一般把时间复杂性和空间复杂
17、性分开，并分别 用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。 （通常，让A隐含在复杂性函数名当中） 2021-7-18算法设计与分析课件21 1.4 算法复杂性分析 最坏情况下的时间复杂性： ),(max max INT(N)T N DI ),(max 1 INet k i ii DI N ),( * 1 INet k i ii ),( * INT 最好情况下的时间复杂性： ),(min min INT(N)T N DI ),(min 1 INet k i ii DI N ) ,( 1 INet k i ii ) ,(INT 平均情况下的时间复杂性： N DI INTIP(N
18、)T),()( avg N DI k i ii INetIP),()( 1 其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*) 达到Tmax(N)的合法输入； 是中使T(N, )达到Tmin(N)的合法 输入；而P(I)是在算法的应用中出现输入I的概率。 I I 2021-7-18算法设计与分析课件22 1.4 算法复杂性分析 算法复杂性在渐近意义下的阶： 渐近意义下的记号：O、o 设f(N)和g(N)是定义在正数集上的正函数。 O的定义的定义：如果存在正的常数C和自然数N0，使得当NN0 时有f(N)Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是 它的一个上界，
19、记为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)。 2021-7-18算法设计与分析课件23 1.4 算法复杂性分析 的定义的定义：如果存在正的常数C和自然数N0，使得当NN0 时有f(N)Cg(N)，则称函数f(N)当N充分大时下有界，且g(N) 是它的一个下界，
20、记为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 o的定义的定义：对于任意给定的0，都存在正整数N0，使 得当NN0时有f(N)/Cg(N),则称函数f(N)当N充分大时的阶 比g(N)低，记为f(N)=o(g(N)。 例如，4NlogN+7=o(3N2+4NlogN+7)。 2021-7-18算法设计与分析课件25 n将要求解的较大规模的问题分割成k个更小规模的子问题。 n T(n/2) T(n/2)T(n/2)T(n/2) T(n) = n对这
21、k个子问题分别求解。如果子问题的规模仍然不够小，则 再划分为k个子问题，如此递归的进行下去，直到问题规模足 够小，很容易求出其解为止。 2021-7-18算法设计与分析课件26 n对这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) n将求出的小规模的问题的解合并为
22、一个更大规模的问题的解， 自底向上逐步求出原来问题的解。 2021-7-18算法设计与分析课件27 n将求出的小规模的问题的解合并为一个更大规模的问题的解， 自底向上逐步求出原来问题的解。 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) 2021-7-18算法设计与分析课件28 n将求出的小规模的问题的解合并为一个更大规模的问题的解， 自底向上逐步求出原来问题的解。 n
23、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) 分治法的设计思想是，将一个难以直接解决的大问题，分治法的设计思想是，将一个难以直接解决的大问题， 分割成一些规模较小的相同问题，以便各个击破，分割成一些规模较小的相同问题，以便各个击破， 分而治之。分而治之。 凡治众如治寡，分数是也。凡治众如治寡，分数是也。 -孙子兵法孙子兵法 2021-7-18算法设计与分析课件29 2.1
24、n直接或间接地调用自身的算法称为递归算法递归算法。用 函数自身给出定义的函数称为递归函数递归函数。 n由分治法产生的子问题往往是原问题的较小模式， 这就为使用递归技术提供了方便。在这种情况下， 反复应用分治手段，可以使子问题与原问题类型 一致而其规模却不断缩小，最终使子问题缩小到 很容易直接求出其解。这自然导致递归过程的产 生。 n分治与递归像一对孪生兄弟，经常同时应用在算 法设计之中，并由此产生许多高效算法。 下面来看几个实例。下面来看几个实例。 2021-7-18算法设计与分析课件30 2.1 例例1 1 阶乘函数阶乘函数 阶乘函数可递归地定义为： 0 0 )!1( 1 ! n n nn
25、n 边界条件边界条件 递归方程递归方程 边界条件与递归方程是递归函数的二个要素，递归函 数只有具备了这两个要素，才能在有限次计算后得出 结果。 2021-7-18算法设计与分析课件31 2.1 例例2 Fibonacci2 Fibonacci数列数列 无穷数列1，1，2，3，5，8，13，21，34，55，被称为 Fibonacci数列。它可以递归地定义为： 边界条件边界条件 递归方程递归方程 1 1 0 )2() 1( 1 1 )( n n n nFnF nF 第n个Fibonacci数可递归地计算如下： public static int fibonacci(int n) if (n 1时
26、，perm(R)由(r1)perm(R1)，(r2)perm(R2)， (rn)perm(Rn)构成。 2021-7-18算法设计与分析课件37 2.1 例例5 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。 2021-7-18算法设计与分析课件38 (2) q(n,m)=
27、q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。 (1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即 n n111 (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 5 整数划分问题整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因 而容易用递归函数直接求解。 在本例中，如果设p(n)为正整
28、数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个 数记作q(n,m)。可以建立q(n,m)的如下递归关系。 2021-7-18算法设计与分析课件39 1 1, 1 ),() 1,( ) 1,(1 ),( 1 ),( mn mn mn mn mmnqmnq nnq nnq mnq 2.1 例例5 5 整数划分问题整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因 而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关 系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个 数记作q(n,m)。可以建
29、立q(n,m)的如下递归关系。 正整数n的划分数p(n)=q(n,n)。 2021-7-18算法设计与分析课件40 2.1 例例6 Hanoi6 Hanoi塔问题塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这 些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号 为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并 仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和 2的前提下，可将圆盘移至 a,b,c中任一塔座上。 2021-7-18算法设计与分
30、析课件41 在问题规模较大时，较难找到一般的方法，因此我们尝试 用递归技术来解决这个问题。 当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直 接移至塔座b上即可。 当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个 较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最 大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照 移动规则从塔座c移至塔座b。 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题， 这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题 的递归算法如下。 2.1 例例6 Hanoi6 Hanoi塔问题塔问题 pub
31、lic 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); 2021-7-18算法设计与分析课件42 优点：优点：结构清晰，可读性强，而且容易用数学归纳法来结构清晰，可读性强，而且容易用数学归纳法来 证明算法的正确性，因此它为设计算法、调试程序带证明算法的正确性，因此它为设计算法、调试程序带 来很大方便。来很大方便。 缺点：缺点：递归算法的运行效率较低，无论是耗费的计算时递归算法的运行效率较低，无论是耗费的计算时 间还是占用的存储空
32、间都比非递归算法要多。间还是占用的存储空间都比非递归算法要多。 2021-7-18算法设计与分析课件43 解决方法：解决方法：在递归算法中消除递归调用，使其转化在递归算法中消除递归调用，使其转化 为非递归算法。为非递归算法。 1.1.采用一个用户定义的栈来模拟系统的递归调用工采用一个用户定义的栈来模拟系统的递归调用工 作栈。该方法通用性强，但本质上还是递归，只作栈。该方法通用性强，但本质上还是递归，只 不过人工做了本来由编译器做的事情，优化效果不过人工做了本来由编译器做的事情，优化效果 不明显。不明显。 2.2.用递推来实现递归函数。用递推来实现递归函数。 3.3.通过通过CooperCoop
33、er变换、变换、反演变换能反演变换能将一些递归转化为将一些递归转化为 尾递归，从而迭代求出结果。尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，后两种方法在时空复杂度上均有较大改善， 但其适用范围有限。但其适用范围有限。 2021-7-18算法设计与分析课件44 n该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决； n该问题可以分解为若干个规模较小的相同问题，即该问题具有该问题可以分解为若干个规模较小的相同问题，即该问题具有 最优子结构性质最优子结构性质 n利用该问题分解出的子问题的解可以合并为该问题的解；利用该问题分解出的子问题的解
34、可以合并为该问题的解； n该问题所分解出的各个子问题是相互独立的，即子问题之间不该问题所分解出的各个子问题是相互独立的，即子问题之间不 包含公共的子问题。包含公共的子问题。 因为问题的计算复杂性一般是随着问题规模的增加 而增加，因此大部分问题满足这个特征。 这条特征是应用分治法的前提，它也是大多数问题 可以满足的，此特征反映了递归思想的应用 能否利用分治法完全取决于问题是否具有这条特征， 如果具备了前两条特征，而不具备第三条特征，则 可以考虑贪心算法贪心算法或动态规划动态规划。 这条特征涉及到分治法的效率，如果各子问题是不 独立的，则分治法要做许多不必要的工作，重复地 解公共的子问题，此时虽然
35、也可用分治法，但一般 用动态规划动态规划较好。 2021-7-18算法设计与分析课件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); /将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的 规模大致相同。即将一个问题分成大小相等的
36、k个子问题的处理方法是 行之有效的。这种使子问题规模大致相等的做法是出自一种平衡平衡 (balancing)子问题子问题的思想，它几乎总是比子问题规模不等的做法要好。 2021-7-18算法设计与分析课件46 一个分治法将规模为n的问题分成k个规模为nm的子问题去解。 设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。 再设将原问题分解为k个子问题以及用merge将k个子问题的解合 并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解 规模为|P|=n的问题所需的计算时间，则有： 1 1 )()/( ) 1 ( )( n n nfmnkT O nT 通过迭代法求得方程
37、的解： 1log 0 log )/()( n m j jj k m mnfknnT 注意注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但 是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值 可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而 当minmi+1时，T(mi)T(n)T(mi+1)。 2021-7-18算法设计与分析课件47 分析：如果n=1即只有一个元素，则只要比较这个元素和x就 可以确定x是否在表中。因此这个问题满足分治法的第一个适 用条件 给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素
38、中找 出一特定元素出一特定元素x。 分析：分析： 该问题的规模缩小到一定的程度就可以容易地解决；该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 2021-7-18算法设计与分析课件48 分析：比较x和a的中间元素amid，若x=amid，则x在L 中的位置就是mid；如果xai，同理我们只 要在amid的后面查找x即可。无论是在前面还是后面查找 x，其方法都和在a中
39、查找x一样，只不过是查找的规模缩 小了。这就说明了此问题满足分治法的第二个和第三个适 用条件。 给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找 出一特定元素出一特定元素x。 2021-7-18算法设计与分析课件49 分析：很显然此问题分解出的子问题相互独立，即在ai的前 面或后面查找x是独立的子问题，因此满足分治法的第四个适 用条件。 给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找 出一特定元素出一特定元素x。 分析：分析： 该问题的规模缩小到一定的程度就可以容易地解决；
40、该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题该问题可以分解为若干个规模较小的相同问题; 分解出的子问题的解可以合并为原问题的解；分解出的子问题的解可以合并为原问题的解； 分解出的各个子问题是相互独立的。分解出的各个子问题是相互独立的。 2021-7-18算法设计与分析课件50 给定已按升序排好序的给定已按升序排好序的n个元素个元素a0:n-1，现要在这，现要在这n个元素中找个元素中找 出一特定元素出一特定元素x。 据此容易设计出二分搜索算法二分搜索算法： public static int binarySearch(int a, int x, int
41、 n) / 在 a0 = a1 = . = an-1 中搜索 x / 找到x时返回其在数组中的位置，否则返回-1 int left = 0; int right = n - 1; while (left amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x 算法复杂度分析：算法复杂度分析： 每执行一次算法的 while循环， 待搜索数 组的大小减少一半。因 此，在最坏情况下， while循环被执行了 O(logn) 次。循环体内 运算需要O(1) 时间， 因此整个算法在最坏情 况下的计算时间复杂性 为O(l
42、ogn) 。 2021-7-18算法设计与分析课件51 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算 u小学的方法：O(n2) 效率太低 u分治法: 复杂度分析复杂度分析 T(n)=O(n2) 没有改进没有改进 1 1 )()2/(4 ) 1 ( )( n n nOnT O nT ab cd X = Y = X = a 2n/2 + b Y = c 2n/2 + d XY = ac 2n + (ad+bc) 2n/2 + bd 2021-7-18算法设计与分析课件52 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以
43、进行两个n n位大整数的乘法运算位大整数的乘法运算 u小学的方法：O(n2) 效率太低 u分治法: XY = ac 2n + (ad+bc) 2n/2 + bd 为了降低时间复杂度，必须减少乘法的次数。 1.XY = ac 2n + (a-c)(b-d)+ac+bd) 2n/2 + bd 2.XY = ac 2n + (a+c)(b+d)-ac-bd) 2n/2 + bd 复杂度分析复杂度分析 T(n)=O(nlog3) =O(n1.59) 较大的改进较大的改进 1 1 )()2/(3 ) 1 ( )( n n nOnT O nT 细节问题细节问题：两个XY的复杂度都是O(nlog3)，但考虑
44、到a+c,b+d可 能得到m+1位的结果，使问题的规模变大，故不选择第2种方案。 2021-7-18算法设计与分析课件53 请设计一个有效的算法，可以进行两个请设计一个有效的算法，可以进行两个n n位大整数的乘法运算位大整数的乘法运算 u小学的方法：O(n2) 效率太低 u分治法: O(n1.59) 较大的改进 u更快的方法? 如果将大整数分成更多段，用更复杂的方式把它们组合起 来，将有可能得到更优的算法。 最终的，这个思想导致了快速傅利叶变换快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算 法，对于大整数乘法，它能在O(nlogn)时间
45、内解决。 是否能找到线性时间的算法？目前为止还没有结果。 2021-7-18算法设计与分析课件54 A和B的乘积矩阵C中的元素Ci,j定义为: n k jkBkiAjiC 1 若依此定义来计算A和B的乘积矩阵C，则每计 算C的一个元素Cij，需要做n次乘法和n-1次 加法。因此，算出矩阵C的 个元素所需的计算 时间为O(n3) u传统方法：O(n3) 2021-7-18算法设计与分析课件55 使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4 个大小相等的子矩阵。由此可将方程C=AB重写为： u传统方法：O(n3) u分治法: 2221 1211 2221 1211 2221 1211
46、 BB BB AA AA CC CC 由此可得： 2112111111 BABAC 2212121112 BABAC 2122112121 BABAC 2222122122 BABAC 复杂度分析复杂度分析 T(n)=O(n3) 没有改进没有改进 2 2 )()2/(8 ) 1 ( )( 2 n n nOnT O nT 2021-7-18算法设计与分析课件56 为了降低时间复杂度，必须减少乘法的次数。 2221 1211 2221 1211 2221 1211 BB BB AA AA CC CC )( 2212111 BBAM 2212112 )(BAAM 1122213 )(BAAM )(
47、1121224 BBAM )( 221122115 BBAAM )( 222122126 BBAAM )( 121121117 BBAAM 624511 MMMMC 2112 MMC 4321 MMC 731522 MMMMC 复杂度分析复杂度分析 T(n)=O(nlog7) =O(n2.81) 较大的改进较大的改进 2 2 )()2/(7 ) 1 ( )( 2 n n nOnT O nT 2021-7-18算法设计与分析课件57 u更快的方法? Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘 积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时 间复杂性，就不能再基于计算
48、22矩阵的7次乘法这样的方法 了。或许应当研究或矩阵的更好算法。 在Strassen之后又有许多算法改进了矩阵乘法的计算时间复 杂性。目前最好的计算时间上界是 O(n2.376) 是否能找到O(n2)的算法？目前为止还没有结果。 2021-7-18算法设计与分析课件58 在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格 不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在 棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定 的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌 不得重叠覆盖。 2021-7-18算法设计与分析课件59 当k0时，将2k2k棋盘分割为4个2k
49、-12k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特 殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可 以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示， 从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用 这种分割，直至棋盘简化为棋盘11。 2021-7-18算法设计与分析课件60 public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割
50、棋盘 / 覆盖左上角子棋盘 if (dr tr + s else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖右下角 boardtr + s - 1tc + s - 1 = t; / 覆盖其余方格 chessBoard(tr, tc, tr+s-1, tc+s-1, s); / 覆盖右上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s, dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角 boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, t
