算法概念介绍及举例说明PPT课件VIP

1、S1:S1:保证保证m=n,m=n,如果如果mnmn，则，则m m、n n的值互换，否则转的值互换，否则转S2.S2.S2:S2:求余数。令求余数。令r=m mod n,r=m mod n,（0=rn)0=rn)S3:S3:判断余数判断余数r r是否为是否为0 0。如果。如果r r是是0 0，则算法终止，则算法终止，n n为为答案，否则转答案，否则转S4.S4.S4:S4:置换。即置换。即m mn,nn,nr,r,转转S2.S2.什么是算法？什么是算法？ 它是一组它是一组有穷规则有穷规则的集合，它规定了解决某一特定类的集合，它规定了解决某一特定类型问题的一系列运算。型问题的一系列运算。 第1页

2、/共197页二、算法的特征二、算法的特征 1 1、确定性、确定性 2 2、能行性、能行性 3 3、输入、输入 4 4、输出、输出 5 5、有穷性、有穷性: :一个算法总是在有限步之后结束，且每一步一个算法总是在有限步之后结束，且每一步都可在有穷时间内完成都可在有穷时间内完成. . 算法与程序的区别：算法与程序的区别： 程序：与某种语言有关，能直接在机器上运行。程序：与某种语言有关，能直接在机器上运行。 算法：与特定的语言无关，可用任何语言实现算法：与特定的语言无关，可用任何语言实现 ，甚至，甚至可以用自然语言实现，但是一般为了避免二义性，本书可以用自然语言实现，但是一般为了避免二义性，本书采用

3、类采用类C C语言描述。语言描述。第2页/共197页 有穷性与有效性的关系有穷性与有效性的关系：三、评价算法的标准三、评价算法的标准 有穷性是对算法的基本要求，如果一个算法要能使用，有穷性是对算法的基本要求，如果一个算法要能使用，必须具有有效性。有效性是指算法在必须具有有效性。有效性是指算法在规定的规定的时间里终止。时间里终止。时间复杂性和空间复杂性时间复杂性和空间复杂性第3页/共197页1.2 1.2 算法设计的步骤算法设计的步骤一、问题的描述一、问题的描述例例: :货郎担问题货郎担问题 设售货员在一天内要到设售货员在一天内要到5 5个城市去推销货物，已知从一个城市去推销货物，已知从一个城市

4、到其他城市的费用，求总费用最少的路线。给出个城市到其他城市的费用，求总费用最少的路线。给出的信息主要有五个城市的关系图及相应的费用矩阵。的信息主要有五个城市的关系图及相应的费用矩阵。二、模型的拟制二、模型的拟制 建模阶段至少要考虑以下两个基本问题：建模阶段至少要考虑以下两个基本问题： 1 1）最适合于这个问题的数学结构是什么？）最适合于这个问题的数学结构是什么？ 2 2）有没有已经解决了的类似问题可供借鉴？）有没有已经解决了的类似问题可供借鉴？第4页/共197页 在模型建立好了以后，应该依据所选定的模型对在模型建立好了以后，应该依据所选定的模型对问题重新陈述问题重新陈述, ,并考虑下列问题并考

5、虑下列问题: : (1)(1)模型是否清楚地表达了与问题有关的所有重要模型是否清楚地表达了与问题有关的所有重要的信息的信息? ?(2)(2)模型中是否存在与要求的结果相关的数学量模型中是否存在与要求的结果相关的数学量? ?(3)(3)模型是否正确反映了输入、输出的关系模型是否正确反映了输入、输出的关系? ?(4)(4)对这个模型处理起来困难吗？对这个模型处理起来困难吗？第5页/共197页32353147214234415721152434724335211 对于货郎担问题，其数学模型是带权图，与此图相关的对于货郎担问题，其数学模型是带权图，与此图相关的是费用矩阵。是费用矩阵。第6页/共197页

6、以货郎担问题为例：采用枚举法。以货郎担问题为例：采用枚举法。分析：分析：三、算法的详细设计三、算法的详细设计 算法的详细设计是指设计求解某个具体问题的算法的详细设计是指设计求解某个具体问题的一系列步骤，并且这些步骤可以通过计算机的各种一系列步骤，并且这些步骤可以通过计算机的各种操作来实现。操作来实现。输入：城市数目输入：城市数目n;n;费用矩阵费用矩阵C=(cC=(cijij) )n n* *n n输出：旅行路线输出：旅行路线TOUR;TOUR;最小费用最小费用MINMIN第7页/共197页Salesman (n) i 1;tour0;min while i=(n-1)! do pPHRMUT

7、I(n-1,i); / PHRMUTI(n-1,i)是生成是生成1到到n-1的第的第i个排列的子过个排列的子过程程 cost(T(p)EFP(c,T(p)； / EFP(c,T)是由费用矩阵是由费用矩阵c及路线及路线T(p)所算得的总费用所算得的总费用 if cost(T(p)=nn=n0 0时，利用时，利用A(n)A(n)的定义和的定义和 一个简单的一个简单的不等式，有不等式，有取取c=|ac=|am m|+|+.+|a.+|a0 0| | 定理得证定理得证. .事实上，只要将事实上，只要将n n0 0取得足够大，可以证明只要取得足够大，可以证明只要c c是比是比|a|am m| |大大的任

8、意一个常数，此定理都成立。的任意一个常数，此定理都成立。10100|( )| |(| /| /)(|)mmmmmmmmA nananaaanannaan定理定理1.1 1.1 若若A(n)=aA(n)=am mn nm m+ + a+ a1 1n+ an+ a0 0是一个是一个m m次多项式，则次多项式，则A(n)=O(nA(n)=O(nm m) )。 第17页/共197页此定理表明，此定理表明，变量变量n n的固定阶数为的固定阶数为m m的任一多项式，的任一多项式，与此多项式的最高阶与此多项式的最高阶n nm同阶，同阶，因此计算时间为因此计算时间为m m阶的阶的多项式的算法，其时间都可用多项

9、式的算法，其时间都可用O(nO(nm).).例如，若一个算例如，若一个算法有数量级为法有数量级为c c1 1n nm1m1, c, c2 2n nm2m2, , , c ck kn nmkmk 的的k k个语句，则个语句，则此算法的数量级就是此算法的数量级就是 c c1 1n nm1m1 +c +c2 2n nm2m2+ +c+ck kn nmkmk 由定理由定理1.11.1，它等于，它等于O(nO(nm m),),其中其中m=maxmm=maxmi i|1|1i k 第18页/共197页n2nlognn=1024104857610240时间（n=1024)1.05s0.01sn=204841

10、9430422528时间（n=2048)4.2s0.02s例子：假设有解决同一个问题的两个算法，它们有例子：假设有解决同一个问题的两个算法，它们有n n个输个输 入，分别要求入，分别要求n n2 2和和nlognnlogn次运算次运算。第19页/共197页定义定义1.3 1.3 如果存在两个正常数如果存在两个正常数c c和和n n0 0, ,对于所有对于所有n nn n0 0, ,有有 |f(n)| c|g(n)|f(n)| c|g(n)| 则记为则记为f(n)=(g(n)f(n)=(g(n)。定义定义1.4 1.4 如果存在两个正常数如果存在两个正常数c1 ,c2,c1 ,c2,和和n n0

11、 0, ,对于所有的对于所有的n n n n0 0, ,有有 则记为则记为f(n)=(g(n)f(n)=(g(n)。 12( )|( ) |( ) |cg nfncg n第20页/共197页五、算法分类（按时间）五、算法分类（按时间） 多项式时间算法：凡可用多项式时间算法：凡可用多项式多项式来对其计算时间界限的算法。来对其计算时间界限的算法。 指数时间算法：计算时间用指数时间算法：计算时间用指数函数指数函数界限的算法。界限的算法。以下六种计算时间的多项式时间算法是最为常见的，其关以下六种计算时间的多项式时间算法是最为常见的，其关系为：系为： O(1) O(logn) O(n) O(nlogn)

12、 O(nO(1) O(logn) O(n) O(nlogn) O(n2 2) O(n) O(n3 3) )指数时间算法一般有指数时间算法一般有O(2O(2n n) )、O(n!) O(n!) 和和O(nO(nn n) )等。其关系为等。其关系为 O(2O(2n n) O(n!) O(n) O(n!) O(nn n) ) 第21页/共197页当数据集的规模很大时，要在现代计算机上运当数据集的规模很大时，要在现代计算机上运行具有比行具有比O O（nlogn)nlogn)复杂度高的算法往往是很困难的。复杂度高的算法往往是很困难的。六、最好、最坏和平均情况六、最好、最坏和平均情况以顺序检索为例以顺序检

13、索为例第22页/共197页第二章第二章 分治法分治法2.1 2.1 方法概述方法概述一、基本思想一、基本思想 1 1、设计思想：将整个问题分成若干个小问题后、设计思想：将整个问题分成若干个小问题后, ,分而治之。分而治之。 2 2、适用条件：、适用条件： 问题规模很大；问题规模很大； 可以分成若干个与原问题性质相同的子问题，并可以可以分成若干个与原问题性质相同的子问题，并可以分别求解。分别求解。 子问题的解通过整合可以得到原问题的解。子问题的解通过整合可以得到原问题的解。 3 3、设计方法：使用递归策略。、设计方法：使用递归策略。第23页/共197页4 4、 设计步骤设计步骤(1)(1)分解：

14、分解：将原问题分解为若干个相互独立、与原问题形式相将原问题分解为若干个相互独立、与原问题形式相同的子问题；同的子问题； (2)(2)求解求解：若子问题容易被解决则直接解，否则再继续分解为：若子问题容易被解决则直接解，否则再继续分解为更小的子问题，直到容易解决；更小的子问题，直到容易解决； (3)(3)合并合并：将已求解的各个子问题的解，逐步合并以得到原问：将已求解的各个子问题的解，逐步合并以得到原问题的解。题的解。第24页/共197页二、分治法的算法设计模式二、分治法的算法设计模式Divide-and-Conquer(n) Divide-and-Conquer(n) /n/n为问题规模为问题规

15、模1 1if n = n0 if n = n0 /n0 /n0 为可解子问题的规模为可解子问题的规模2 2then then 3 3 4 4 解子问题解子问题5 5 return( return( 子问题的解子问题的解 ) )6 6 4 4for i for i 1 to k 1 to k /分解为分解为k k个子问题个子问题5 5 do yi do yi Divide-and-Conquer(|Pi|)/ Divide-and-Conquer(|Pi|)/递归解决递归解决PiPi6 6 T T MERGE(y1,y2,.,yk) MERGE(y1,y2,.,yk) /合并子问题合并子问题7

16、7 return Treturn T递归过程递归过程注意：分治法可以用递归实现，也可以用循环实现。注意：分治法可以用递归实现，也可以用循环实现。第25页/共197页 其中：其中其中：其中|P|P|表示问题表示问题P P的规模；的规模；n0n0为一阈值，表示为一阈值，表示当问题当问题P P的规模不超过的规模不超过n0n0时，问题已容易直接解出，不必时，问题已容易直接解出，不必再继续分解。算法再继续分解。算法MERGE(y1,y2,.,yk)MERGE(y1,y2,.,yk)是该分治法中的是该分治法中的合并子算法，用于将合并子算法，用于将P P的子问题的子问题P1 ,P2 ,.,PkP1 ,P2

17、,.,Pk的相应的的相应的解解y y1 1,y,y2 2,.,y,.,yk k合并为合并为P P的解。的解。第26页/共197页： 其中，其中，T(n)T(n)是输入规模为是输入规模为n n的的Divide-and-ConquerDivide-and-Conquer的的时间，时间，g(n)g(n)是对足够小的输入规模能直接计算出答案是对足够小的输入规模能直接计算出答案的时间，的时间，f(n)f(n)是是MERGEMERGE的时间。的时间。 倘若所分成的两个子问题的输入规模大致相等，则倘若所分成的两个子问题的输入规模大致相等，则Divide-and-ConquerDivide-and-Conqu

18、er总的计算时间可以用下面的递推关系总的计算时间可以用下面的递推关系来表示：来表示： (n(n足够小足够小) ) ( (否则否则) ) )()2/(2)()(nfnTngnT第27页/共197页2.2 2.2 二二 分分 检检 索索一、问题描述一、问题描述 已知一个按非降次序排列的元素表已知一个按非降次序排列的元素表a a1 1,a,a2 2, ,a an n, ,要求判定要求判定某给定元素某给定元素x x是否在该表中出现。若是，则找出是否在该表中出现。若是，则找出x x在表中的在表中的位置，并将此下标值赋给变量位置，并将此下标值赋给变量j j；若非，则将；若非，则将j j置成置成0 0。二、

19、问题分析二、问题分析 设该问题用设该问题用I=(n, aI=(n, a1 1,a,a2 2, ,a an n,x),x)来表示，可以将它分解来表示，可以将它分解成一些子问题，一种可能的做法是，选取一个下标成一些子问题，一种可能的做法是，选取一个下标k k，由此得到，由此得到三个子问题：三个子问题：I I1 1=(k-1, a=(k-1, a1 1,a,a2 2, ,a ak-1k-1,x),I,x),I2 2=(1,a=(1,ak k,x),x)和和I I3 3=(n-k, =(n-k, a ak+1k+1, ,a an n,x),x)。第28页/共197页 对于对于I I2 2，通过比较，通

20、过比较x x和和a ak k容易得到解决。如果容易得到解决。如果x= ax= ak k, ,则则j=kj=k且且不需再对不需再对I I1 1和和I I3 3求解；否则，在求解；否则，在I I2 2 子问题的子问题的j=0j=0，此时若，此时若xaxaxak k, ,只有只有I I3 3留待留待求解，在求解，在I I1 1子问题中的子问题中的j=0j=0。在。在a ak k作了比较之后，留待求解的作了比较之后，留待求解的问题（如果有的话）可以再一次使用分治法来求解。如果对问题（如果有的话）可以再一次使用分治法来求解。如果对所求解的问题（或子问题）所选的下标所求解的问题（或子问题）所选的下标k k

21、都是其元素的中间元都是其元素的中间元素下标（例如，对于素下标（例如，对于I I，k=(n+1)/2k=(n+1)/2）, ,则所产生的算法就是则所产生的算法就是通常所说的二分检索。通常所说的二分检索。第29页/共197页三、二分检索算法三、二分检索算法 算法算法2.3 2.3 二分检索二分检索 /给定一个按非降次序排列的元素数组给定一个按非降次序排列的元素数组A(1:n),n1,A(1:n),n1,判判 断断x x是否出现。若是，置是否出现。若是，置j j，使得，使得x=A(j),x=A(j),若非，若非，j=0/j=0/BINSEARCH(A,n,x)BINSEARCH(A,n,x)1 lo

22、w 1 low 1 12 high 2 high n n 第30页/共197页3 3 while low=highwhile lowhighlowhigh，数组，数组A A中没有找到中没有找到x x，返回，返回j j0 04 do4 do5 5 6 6 / /取处于取处于lowlow和和highhigh之间的中间值之间的中间值7 if x=Amid/7 if x=Amid/找到值为找到值为x x的元素，的元素，midmid即为其下标，返回即为其下标，返回midmid8 then8 thenreturn midreturn mid9 else if x Amid9 else if x Amid/

23、如果如果x Amidx Amid，则，则x x可能位于可能位于lowlow与与midmid之间，之间，1010 /否则否则x x可能位于可能位于midmid与与highhigh之间之间1111 then high then high mid - 1 mid - 11212 else low else low mid + 1 mid + 113 13 14 retrun 014 retrun 0 ()/2midlowhigh非递归形式非递归形式第31页/共197页四、算法的证明四、算法的证明假定在假定在A9A9中顺序存放着以下中顺序存放着以下9 9个元素：个元素：-15-15，-6-6，0 0，

24、7 7，9 9，2323，5454，8282，101101。要求检索下列。要求检索下列x x的值：的值：101101，-14-14和和8282是否是否在在A A中出现。中出现。 X=101low high midX=-14low high midX=82low high mid19519519569714269789811199921找不到898找到找到第32页/共197页A（1） （2） （3） （4） （5） （6） （7） （8） （9）元素-15-6079235482101比较次数323413234从算法中可以看到从算法中可以看到, ,所有的运算基本上都是进行比较和所有的运算基本上都是

25、进行比较和数据传送，前两条是赋值语句数据传送，前两条是赋值语句, ,频率计数均为频率计数均为1 1。在。在whilewhile循循环中，我们集中考虑循环的次数，而其他运算的频率计数显环中，我们集中考虑循环的次数，而其他运算的频率计数显然与这些元素比较运算的频率计数具有相同的数量级，找到然与这些元素比较运算的频率计数具有相同的数量级，找到这九个元素中的每一个所需的元素循环的次数如下：这九个元素中的每一个所需的元素循环的次数如下： 第33页/共197页 (1) (log n) (log n) (log n) (log n) (log n) 不成功检索成功检索平均情况不成功检索成功检索最坏情况不成功

26、检索成功检索最佳情况第34页/共197页 分析：对于分析：对于A A中的中的n n个数，如果个数，如果x x在在A A中出现，则是成功检索，所中出现，则是成功检索，所以成功检索共有以成功检索共有n n种情况，而不成功的检索，种情况，而不成功的检索，x x将取将取n+1n+1个区间中的个区间中的不同值，因此在计算出不同值，因此在计算出x x在这在这2n+12n+1种情况下的执行时间后，就可以种情况下的执行时间后，就可以求出其在各种情况下的时间复杂性了。求出其在各种情况下的时间复杂性了。例子：例子：A： （1） （2） （3） （4） （5） （6） （7） （8 ） （9 ） 元素：元素： -1

27、5 -6 0 7 9 23 54 82 101 比较次数：比较次数： 3 2 3 4 1 3 2 3 4第35页/共197页 成功检索的比较次数是成功检索的比较次数是25/92.77。 不成功检索有不成功检索有1010种，如果种，如果xAxA（1 1）,A(1)xA(2), ,A(1)xA(2), A(2)xA(3), A(5)xA(6),A(6)xA(7),A(7)xA(8)A(2)xA(3), A(5)xA(6),A(6)xA(7),A(7)xA(8) ，为了判，为了判断断x不在不在A中，算法要比较中，算法要比较3次，而其余的情况要比较次，而其余的情况要比较4次，因此一次，因此一次不成功检

28、索的元素平均比较次数就是（次不成功检索的元素平均比较次数就是（3+3+3+4+4+3+3+3+4+4）/10=3.4 。 第36页/共197页 （1）此树的结点由此树的结点由内结点和外结点内结点和外结点组成；组成； （2）每个内结点表示一次元素比较，用）每个内结点表示一次元素比较，用圆形结点圆形结点表示，在表示，在以元素比较为基础的二分检索中，每个内结点存放一个以元素比较为基础的二分检索中，每个内结点存放一个mid值；值； （3） 外结点用外结点用方形结点方形结点表示，在二分检索中它表示一次不表示，在二分检索中它表示一次不成功的检索；成功的检索； （4）x如果在如果在A 中出现，则算法就在一个

29、圆形结点处结束，中出现，则算法就在一个圆形结点处结束，该结点将指出该结点将指出x在在A中的下标；中的下标； x如果不在如果不在A 中出现，则算法中出现，则算法就在一个方形结点处结束，如图所示。就在一个方形结点处结束，如图所示。第37页/共197页529713486xA(1)A(1)xA(2)A(3)xA(4)A(2)xA(3)A(6)xA(7)A(5)xA(6)A(4)xA(5)A(8)xA(9)A(7)xA(8)第38页/共197页证明：考察以证明：考察以n n个结点描述个结点描述BINSRCHBINSRCH执行过程的二元比较树，执行过程的二元比较树，所有成功检索都在内部结点处结束，而所有不

30、成功的检索都所有成功检索都在内部结点处结束，而所有不成功的检索都在外部结点处结束在外部结点处结束。由于。由于2 2k-1k-1n n2 2k k ，因此所有的内部结点在，因此所有的内部结点在1 1，2 2，3 3，k k级，而所有的外部结点在级，而所有的外部结点在k,k+1k,k+1级（注意：根级（注意：根在在1 1 级）。即是，成功检索在级）。即是，成功检索在i i级终止所需要的元素比较次数级终止所需要的元素比较次数是是i,i,而而不成功检索在不成功检索在i i级外部结点终止的元素比较数是级外部结点终止的元素比较数是i-1.i-1.因因此定理得证。此定理得证。 定理定理2.1 2.1 若若n

31、 n在区域在区域22k-1k-1, 2, 2k k) )中，则对于一次成功的检索，中，则对于一次成功的检索，BINSRCH BINSRCH 至多作至多作k k次比较，而对于一次不成功的检索，或者作次比较，而对于一次不成功的检索，或者作k-1k-1次比较或者作次比较或者作k k次比较。次比较。第39页/共197页 由此：最坏情况下的成功检索和不成功检索的计算时间是由此：最坏情况下的成功检索和不成功检索的计算时间是（lognlogn）, ,最好情况下的成功检索在根结点处到达，时间是最好情况下的成功检索在根结点处到达，时间是（1 1），），而最好情况的不成功检索要而最好情况的不成功检索要lognlo

32、gn次元素比较，所以次元素比较，所以时间是时间是（lognlogn）。由于外部节点都在。由于外部节点都在k k和和k+1k+1级，因此，每级，因此，每种不成功检索的时间都是种不成功检索的时间都是（lognlogn），），故平均情况下不成功故平均情况下不成功检索的计算时间是检索的计算时间是（lognlogn）。 第40页/共197页 E=I+2n E=I+2n (1) (1)令令S(n)S(n)是成功检索的平均比较数，则是成功检索的平均比较数，则 S S（n)=I/n+1n)=I/n+1 (2) (2) 平均情况下成功检索的时间复杂性分析：平均情况下成功检索的时间复杂性分析： 设根到所有内部结点

33、的距离之和称为内部路径长度设根到所有内部结点的距离之和称为内部路径长度I I，由根到所有外部结点的距离之和称为外部路径长度由根到所有外部结点的距离之和称为外部路径长度E E，可以，可以证明：证明：为什么要为什么要+1+1第41页/共197页 令令U U（n)n)是不成功检索的平均情况比较数，而任何一个是不成功检索的平均情况比较数，而任何一个外部结点所需要的比较数是由根到该结点路径的长度，由外部结点所需要的比较数是由根到该结点路径的长度，由此得：此得： U(n)=E/(n+1)U(n)=E/(n+1) (3) (3)利用（利用（1 1）- -（3 3）可以得到：）可以得到： S(n)=(1+1/

34、n)U(n)-1S(n)=(1+1/n)U(n)-1因此：平均情况下成功检索的时间复杂性为：因此：平均情况下成功检索的时间复杂性为： (log n)。第42页/共197页五、一种二分检索的变形五、一种二分检索的变形BINSEARCH1BINSEARCH1。 BINSEARCH1BINSEARCH1的的whilewhile循环中循环中x x和和AmidAmid之间只用作一次比较。之间只用作一次比较。 BINSEARCH1(A,n,x,j)1 low 12 high n+13 while low high4do56 mid (low + high) / 27 if (x Amid)/在循环中只比较

35、一次8 then high mid9else lowmid10 11 if x = Alow12 then j low/x出现13 else j=0 / x不出现14 return j第43页/共197页 BINSEARCHBINSEARCH和和BINSEARCH1BINSEARCH1相比较可看出，对于任何一种成相比较可看出，对于任何一种成功的检索，功的检索，BINSEARCH1BINSEARCH1平均要比平均要比BINSEARCHBINSEARCH多作多作 次比较。次比较。BINSEARCH1BINSEARCH1的最好、平均和最坏情况时间对于成的最好、平均和最坏情况时间对于成功和不成功的检索

36、都是功和不成功的检索都是 。)(log nO)(log nO)(log nO2/ )n(log第44页/共197页 六、以比较为基础检索的时间下界六、以比较为基础检索的时间下界 1. 什么是以比较为基础的检索算法什么是以比较为基础的检索算法 检索一给定元素检索一给定元素x是否在是否在A中出现。如果只允许进行元素中出现。如果只允许进行元素间的比较而不允许对它们实施运算，在这种条件下所设计的间的比较而不允许对它们实施运算，在这种条件下所设计的算法都称为是以比较为基础的算法算法都称为是以比较为基础的算法 。 2. 二分检索是以比较为基础的检索算法中最坏情况下的最优二分检索是以比较为基础的检索算法中最

37、坏情况下的最优算法算法. 第45页/共197页 定理定理2.3 2.3 设设A A（1 1：n n）含有）含有n n个不同的元素，个不同的元素，n1n1，它们，它们被排序为被排序为A(1)A(2)A(1)A(2)A(n)A(n)。又设用以比较为基础去判。又设用以比较为基础去判断是否断是否xAxA（1 1：n n）的任何算法在最坏情况下所需的最小）的任何算法在最坏情况下所需的最小比较次数是比较次数是FINDFIND（n n），那么），那么FINDFIND（n n）log(1)n 第46页/共197页 结论：结论：由于二分检索所产生的比较树中所有的外部结点都由于二分检索所产生的比较树中所有的外部结

38、点都在相邻接的两个级上在相邻接的两个级上，不难证明这样的二元树使得由根到不难证明这样的二元树使得由根到结点的最长路径减至最小，因此，结点的最长路径减至最小，因此，二分检索是解决检索问二分检索是解决检索问题在最坏情况下的最优算法。题在最坏情况下的最优算法。证明：通过考虑模拟求解检索问题的各种算法的比较树可证明：通过考虑模拟求解检索问题的各种算法的比较树可知，知，FINDFIND（n n）不大于树中根到一个叶子最长路径的距离。）不大于树中根到一个叶子最长路径的距离。在这所有的树中都必定有在这所有的树中都必定有n n个内结点与个内结点与x x在在A A中可能的中可能的n n种出种出现相对应，如果一棵

39、二元树的所有内结点所在的级数小于现相对应，如果一棵二元树的所有内结点所在的级数小于级数级数k k，则最多有，则最多有2 2k k-1-1个内结点，因此个内结点，因此n 2n 2k k-1,-1,即即FINDFIND（n n）=k=k ) 1log( n第47页/共197页一、直接求最大、最小元素一、直接求最大、最小元素算法算法2.5 2.5 直接找最大和最小元素直接找最大和最小元素maxmin(A,n) maxmin(A,n) /将将A(1:n)A(1:n)中的最大元素置于中的最大元素置于maxmax，最小元素置于，最小元素置于min/min/1 max 1 max A1A12 min 2 m

40、in A1;A1;3 for i 3 for i 2 to n2 to n4 4 dodo5 5 6 6 if max Ai if max Ai 6 if min Ai 7 7 then min then min AiAi8 8 2.3 2.3 找最大和最小元素找最大和最小元素 第48页/共197页时间复杂性分析：时间复杂性分析： STRAITMAXMIN在最好、平均和最坏情况下均需要作在最好、平均和最坏情况下均需要作2(n-1)次元素比较。次元素比较。 第49页/共197页如果稍做修改：如果稍做修改： 用下面的语句代替用下面的语句代替forfor循环中的语句：循环中的语句： if A(i)m

41、ax then maxif A(i)max then maxA(i)A(i) else if A(i)min then min else if A(i)min then minA(i) A(i) endif endif endif endif 最好情况将在元素按递增次序排列时出现，元素比较最好情况将在元素按递增次序排列时出现，元素比较数是数是n-1n-1；最坏情况将在递减次序时出现，元素比较是；最坏情况将在递减次序时出现，元素比较是 2 2（n-1n-1）；至于在平均情况下）；至于在平均情况下,A(i),A(i)将有一半的时间比将有一半的时间比maxmax大，因此平均比较数是大，因此平均比较数

42、是3/2(n-1)3/2(n-1)。第50页/共197页二、用分治法求最大、最小元素二、用分治法求最大、最小元素 1、问题分析、问题分析 使用分治策略设计是将任一实例使用分治策略设计是将任一实例I=(n，A(1)，A(n)分成一些较小的实例来处理，例如，可以把分成两个这样分成一些较小的实例来处理，例如，可以把分成两个这样的实例的实例I1=(n/2，A(1)，A(n/2)和和 =(n-n/2,A(n/2+1),A(n)。如果。如果()和（）和（）是中的最大和最小元素，则是中的最大和最小元素，则（）等于（）等于（）和（）和（）中的大者，（）等于）中的大者，（）等于（）和（）和（）中的小者。如果只包

43、含一个元）中的小者。如果只包含一个元素，则不需要作任何分割直接就可得到其解。素，则不需要作任何分割直接就可得到其解。 2I第51页/共197页2.2.算法算法算法算法. .递归求取最大和最小元素递归求取最大和最小元素float An;float An;maxminmaxmin（i, j, fmax, fmini, j, fmax, fmin）/最大和最小元素赋给最大和最小元素赋给fmaxfmax和和fminfmin1 if i = j 1 if i = j 2 2 then then3 3 4 4 fmax fmax Ai; Ai;5 5 fmin fmin Ai; Ai;6 6 第52页/共

44、197页7 else if i = j-17 else if i = j-18 8 then if AiAj then if Ai rmax if lmax rmax25 25 then fmax then fmax lmax; lmax;26 else fmax 26 else fmax rmax rmax27 if lmin rmin27 if lmin rmin28 28 then fmin then fmin rmin; rmin;29 else fmin 29 else fmin lmin; lmin;30 30 递归调用递归调用第54页/共197页考虑如下例子：考虑如下例子：A A

45、：（：（1 1） （2 2） （3 3） （4 4） （5 5） （6 6） （7 7） （8 8） （9 9） 22 13 -5 -8 15 60 17 31 4722 13 -5 -8 15 60 17 31 47第55页/共197页3.时间复杂性分析时间复杂性分析 0 n=1 (n)= 1 n=2 n2当当n是的幂时，即对于某个正整数是的幂时，即对于某个正整数k，nk ，有，有 T(n)=2T(n/2)+2=2(2T(n/4)+2)+2=4T(n/4)+4+2 =k-1 T(2)+ =k-1 T+k-2 =3n/2-2(/2 )(/2 )2TnTn112ki k ?第56页/共197页讨

46、论：以上算法是否是最优的？讨论：以上算法是否是最优的？1 1）递归带来的额外的空间开销。）递归带来的额外的空间开销。2 2）当元素当元素A(i)A(i)和和A(j)A(j)的比较时间的比较时间i i和和j j的比较时间相差不大的比较时间相差不大时，过程时，过程maxminmaxmin并不可取。并不可取。因此：当因此：当n是的幂时，是的幂时，3n/2-2是最好，平均及最坏情况的比是最好，平均及最坏情况的比较数较数,和直接算法的比较数和直接算法的比较数n相比，它少了。相比，它少了。 可以证明，任何一种以元素比较为基础的找最大和最小元素可以证明，任何一种以元素比较为基础的找最大和最小元素的算法，其元

47、素比较下界均为的算法，其元素比较下界均为 次。次。 3 /22n第57页/共197页 为说明问题，假设元素比较与为说明问题，假设元素比较与i和和j间的比较时间相同，又设间的比较时间相同，又设maxmin的频率计数为的频率计数为C(n) ，n=2k，,k是某个正整数，并且对是某个正整数，并且对前两种情况，用前两种情况，用ij-1来代替来代替i=j和和i=j-1这两次比较，这样，这两次比较，这样，只用对只用对i和和j-1作一次比较就足以实现被修改过的语句。于是作一次比较就足以实现被修改过的语句。于是maxmin频率计数频率计数 C(n)= C(n)= n=2 n23) 2/(22nC? ?第58页

48、/共197页解此关系式可得解此关系式可得 C(n)=2C(n/2)+3=4C(n/4)+6+3C(n)=2C(n/2)+3=4C(n/4)+6+3 =2 =2k-1k-1C(2)+C(2)+ =2=2k k+3+3* *2 2k-1k-1-3-3 =5n/2-3 =5n/2-30232ii k 分析：分析：STRAITMAXMINSTRAITMAXMIN的比较数是的比较数是3(n-1)(3(n-1)(包括实现包括实现forfor循环所循环所要的比较要的比较) )。尽管它比。尽管它比5n/2-35n/2-3大些，但由于递归算法中大些，但由于递归算法中i i，j j，fmaxfmax，fminfm

49、in进出栈所带来的开销，因此进出栈所带来的开销，因此maxminmaxmin在这种情况下在这种情况下反而比反而比STRAITMAXMINSTRAITMAXMIN还要慢些。还要慢些。第59页/共197页 第60页/共197页2.42.4斯特拉森矩阵乘法斯特拉森矩阵乘法一、一般的矩阵乘法一、一般的矩阵乘法 设设C=AC=A* *B,B, 则利用常规方法计算，所需时间是则利用常规方法计算，所需时间是 3()n二、二、分治法分治法求矩阵乘法求矩阵乘法 设设n=2n=2k k，则可以将两个矩阵的乘法做如下划分：，则可以将两个矩阵的乘法做如下划分：nkjkBkiAjiC1),(),(),(22211211

50、2221121122211211CCCCBBBBAAAA1, i jn第61页/共197页其中：其中：C C1111=A=A1111B B1111+A+A1212B B2121 C C1212=A=A1111B B1212+A+A1212B B2121 C C2121=A=A2121B B1111+A+A2222B B2121 C C2222=A=A2121B B1212+A+A2222B B2222可以证明可以证明: : C=AB= C=AB= 22211211CCCC第62页/共197页三三. .斯特拉森矩阵乘法斯特拉森矩阵乘法 斯特拉森矩阵乘法的设计思想斯特拉森矩阵乘法的设计思想: :增

51、加加法的次数增加加法的次数, ,减少乘减少乘法的次数法的次数. . 如果分块矩阵的级大于如果分块矩阵的级大于2,2,则可以继续将这些子矩阵分成则可以继续将这些子矩阵分成更小的方阵更小的方阵, ,直至每个方阵只含有一个元素直至每个方阵只含有一个元素, ,以至可以直接以至可以直接计算其乘积计算其乘积. .时间复杂性分析时间复杂性分析: n 2 n2则则T(n)=O(n3)2)2/(8)(dnnTbnT第63页/共197页先用七个乘法和十个加（减）法来算出以下的先用七个乘法和十个加（减）法来算出以下的P-VP-VP=(AP=(A1111+A+A2222)(B)(B1111+B+B2222) ) ，Q

52、=(AQ=(A2121+A+A2222)B)B1111R=AR=A1111(B(B1212-B-B2222) )， S=AS=A2222(B(B2121-B-B1111) )T=(AT=(A1111+A+A1212)B)B2222 ，U=(AU=(A2121-A-A1111)(B)(B1111+B+B1212) )V=(AV=(A1212-A-A2222)(B)(B2121+B+B2222) )然后用然后用8 8个加减法算出这些个加减法算出这些 C Cij ij C C1111=P+S-T+V=P+S-T+VC C1212=R+T=R+TC C2121=Q+S=Q+SC C2222=P+R-Q

53、+U=P+R-Q+U 第64页/共197页以上共用了以上共用了7次乘法次乘法,18次加减法次加减法. n 2 n2 其中其中a和和b是常数。是常数。解：解：T(n)=7T(n/2)+an2=72T(n2/4)+(7/4)an2+an2 =73T(n3/8)+(7/4)2an2+(7/4)an2+an2 =an2(1+(7/4)+(7/4)2+.+(7/4)k-1)+7kT(1)cn2(7/4)logn+7logn(1)2) 2/(7)(annTbnT第65页/共197页因为：因为：7logn =nlog7 cn2(7/4)logn=cnlog4*nlog7-log4=cnlog4+log7-l

54、og4=cnlog7因此上式因此上式(1)=cnlog7+7logn=cnlog7+nlog7=(c+1)nlog7=O(nlog7)O(n2.81).第66页/共197页（1 1）当）当n n小于小于120120时，斯特拉森矩阵乘法与普通的乘法没时，斯特拉森矩阵乘法与普通的乘法没有太大的区别有太大的区别 。（2 2）斯特拉森矩阵乘法的核心就是降低乘法的次数而增）斯特拉森矩阵乘法的核心就是降低乘法的次数而增加加法的次数，那么是否可以使乘法由加加法的次数，那么是否可以使乘法由7 7次降低为次降低为6 6次呢？次呢？已经证明已经证明7 7次是必须的，这一方面改进只能从更高维数如次是必须的，这一方面

55、改进只能从更高维数如3 3* *3 3，或，或4 4* *4 4并用递归分治的合并方法来实现，现在可以达并用递归分治的合并方法来实现，现在可以达到到o(no(n2.4953642.495364).).第67页/共197页一、基本方法一、基本方法1 1例子：例子：背包问题背包问题：已知有：已知有n n种物品和一个容量大小为种物品和一个容量大小为M M的背包，每种物品的背包，每种物品i i的容量为的容量为w wi i。假定将物品假定将物品i i的一部分的一部分x xi i放入背包就会得到放入背包就会得到p pi ix xi i的效益，的效益，这里，这里，0 0 x xi i1 1，p pi i0

56、0。采用怎样的装包方法才会使装入背包物。采用怎样的装包方法才会使装入背包物品的总效益最大呢？显然，由于背包容量是品的总效益最大呢？显然，由于背包容量是M M，因此，要求所有选，因此，要求所有选中要装入背包的物品总容量不得超过中要装入背包的物品总容量不得超过M M。如果这。如果这n n件物品的总容量件物品的总容量不超过不超过M M，则把所有物品装入背包自然获得最大效益。，则把所有物品装入背包自然获得最大效益。如果这些物品容量的和大于如果这些物品容量的和大于M M，则在这种情况下该如何装包呢？，则在这种情况下该如何装包呢？第三章贪心方法第三章贪心方法3 31 1方法概述方法概述第68页/共197页

57、例例: :考虑下列情况下的背包问题：考虑下列情况下的背包问题：n=3n=3，M M2020， (25(25，2424，1515）, =(18,15,10), =(18,15,10)。其中的四个可行解是。其中的四个可行解是: : （1/2,1/3,1/41/2,1/3,1/4） 16.5 16.5 24.2524.25（1 1，2/152/15，0 0） 20 20 28.228.2（0 0，2 23 3，1 1） 20 20 3131（0 0，1 1，1 12 2） 20 20 31.531.5niiixw1niiixp1123(,)xxx123(,)ppp123(,)www第69页/共197

58、页2 2、 适用条件：适用条件：（1 1）有）有n n个输入；个输入；（2 2）它的解就由这）它的解就由这n n个输入的个输入的某个子集某个子集组成；组成；（3 3）这个子集必须满足一定的约束条件）这个子集必须满足一定的约束条件-可行解；可行解；（4 4）可行解一般不止一个，但是）可行解一般不止一个，但是 第70页/共197页3 3有关概念有关概念（1 1） 把子集必须满足的基本条件称为约束条件。把子集必须满足的基本条件称为约束条件。（2 2） ：把满足约束条件的子集称为该问题的可行解。：把满足约束条件的子集称为该问题的可行解。（3 3） （可行解一般来说是不唯一的）为了衡量可（可行解一般来说

59、是不唯一的）为了衡量可行解的优劣，事先也给出了一定的标准，这些标准一般以用函行解的优劣，事先也给出了一定的标准，这些标准一般以用函数形式给出，这些函数称为目标函数。数形式给出，这些函数称为目标函数。（4 4） 那些使目标函数取极值（极大或极小）的可行那些使目标函数取极值（极大或极小）的可行解，称为最优解解，称为最优解。第71页/共197页4 4基本方法：基本方法： 贪心方法是一种改进了的分级处理方法。它首先根据题意，选贪心方法是一种改进了的分级处理方法。它首先根据题意，选取一种量度标准。然后按这种量度标准对这取一种量度标准。然后按这种量度标准对这n n个输入排序，并按序个输入排序，并按序一次输

60、入一个量。如果这个输入和当前已构成在这种量度意义下的一次输入一个量。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法称分解中。这种能够得到某种量度意义下的最优解的分级处理方法称为贪心方法。为贪心方法。注意：注意：。第72页/共197页二、贪心方法的算法设计模式二、贪心方法的算法设计模式GREEDYGREEDY（A A，n n）/An /An 包含包含n n个输入个输入/1 solution1 solution / /将解向量将解向