《算法概念介绍及举例说明.pptx》由会员分享，可在线阅读，更多相关《算法概念介绍及举例说明.pptx（197页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、S1:保保证m=n,如果如果mn，则m、n的的值互互换，否，否则转S2.S2:求余数。令求余数。令r=m mod n,（0=rn)S3:判断余数判断余数r是否是否为0。如果。如果r是是0，则算法算法终止，止，n为答案，否答案，否则转S4.S4:置置换。即。即mn,nr,转S2.什么是算法？什么是算法？它是一它是一组有有穷规则的集合，它的集合，它规定了解决某一特定定了解决某一特定类型型问题的一系列运算。的一系列运算。第1页/共197页二、算法的特征二、算法的特征1、确定性、确定性2、能行性、能行性3、输入入4、输出出5、有、有穷性性:一个算法一个算法总是在有限步之后是在有限步之后结束，且每一步束
2、，且每一步都可在有都可在有穷时间内完成内完成.算法与程序的区算法与程序的区别：程序：与某种程序：与某种语言有关，能直接在机器上运行。言有关，能直接在机器上运行。算法：与特定的算法：与特定的语言无关，可用任何言无关，可用任何语言言实现，甚至，甚至可以用自然可以用自然语言言实现，但是一般，但是一般为了避免二了避免二义性，本性，本书采用采用类C语言描述。言描述。第2页/共197页 一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就一个算法总是在执行了有穷步骤的运算后终止，否则就是一个计算过程。是一个计算过程
3、。是一个计算过程。是一个计算过程。有有穷性与有效性的关系性与有效性的关系：三、三、评价算法的价算法的标准准 有有穷性是性是对算法的基本要求，如果一个算法要能使用，必算法的基本要求，如果一个算法要能使用，必须具有有效性。有效性是指算法在具有有效性。有效性是指算法在规定的定的时间里里终止。止。时间复复杂性和空性和空间复复杂性性第3页/共197页1.2 算法算法设计的步的步骤一、一、问题的描述的描述例例:货郎担郎担问题设售售货员在一天内要到在一天内要到5个城市去推个城市去推销货物，已知从一物，已知从一个城市到其他城市的个城市到其他城市的费用，求用，求总费用最少的路用最少的路线。给出出的信息主要有五个
4、城市的关系的信息主要有五个城市的关系图及相及相应的的费用矩用矩阵。二、模型的二、模型的拟制制建模建模阶段至少要考段至少要考虑以下两个基本以下两个基本问题：1）最适合于）最适合于这个个问题的数学的数学结构是什么？构是什么？2）有没有已）有没有已经解决了的解决了的类似似问题可供借可供借鉴？第4页/共197页 在模型建立好了以后，在模型建立好了以后，应该依据所依据所选定的模型定的模型对问题重新重新陈述述,并考并考虑下列下列问题:(1)模型是否清楚地表达了与模型是否清楚地表达了与问题有关的所有重要有关的所有重要的信息的信息?(2)模型中是否存在与要求的模型中是否存在与要求的结果相关的数学量果相关的数学
5、量?(3)模型是否正确反映了模型是否正确反映了输入、入、输出的关系出的关系?(4)对这个模型个模型处理起来困理起来困难吗？第5页/共197页152434724335211 对于于货郎担郎担问题，其数学模型是，其数学模型是带权图，与此，与此图相关的相关的是是费用矩用矩阵。第6页/共197页以货郎担问题为例：采用枚举法。以货郎担问题为例：采用枚举法。分析：分析：三、算法的三、算法的详细设计 算法的算法的详细设计是指是指设计求解某个具体求解某个具体问题的一系的一系列步列步骤，并且，并且这些步些步骤可以通可以通过计算机的各种操作算机的各种操作来来实现。输入：城市数目入：城市数目n;费用矩用矩阵C=(c
6、ij)n*n输出：旅行路出：旅行路线TOUR;最小最小费用用MIN第7页/共197页Salesman(n)i 1;tour0;min while i=(n-1)!do pPHRMUTI(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)=n0时，利用，利用A(n)的定的定义和和 一个一个简单的的不等式，有不等式，有取取c=|am|+.+|a0|定理得定理得证.事事实上，只要将上，只要将n0取得
7、足取得足够大，可以大，可以证明只要明只要c是比是比|am|大的大的任意一个常数，此定理都成立。任意一个常数，此定理都成立。定理定理1.1 若若A(n)=amnm+a1n+a0是一个是一个m次多次多项式，式，则A(n)=O(nm)。第17页/共197页此定理表明，此定理表明，变量变量n n的固定阶数为的固定阶数为m m的任一多项式，的任一多项式，与此多项式的最高阶与此多项式的最高阶n nm同阶，同阶，因此计算时间为因此计算时间为m m阶的阶的多项式的算法，其时间都可用多项式的算法，其时间都可用O(nO(nm).).例如，若一个算例如，若一个算法有数量级为法有数量级为c c1 1n nm1m1,c
8、,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=2048419430422528时间（n=2048)4.2s0.02s例子：假例子：假设有解决同一个有解决同一个问题的两个算法，它的两个算法，它们有有n个个输入
9、，分入，分别要求要求n2和和nlogn次运算次运算。第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 0,对于所有的对于所有的n n n n0 0,有有 则记为则记为f(n)=(g(n)f(n)=(g(n)。一个算法的一个算法的一个算法的一个算法的f(n)=(g(n)f(n)=(g(n)f(n)=(g(
10、n)f(n)=(g(n)意味着该算法在最好和最坏情意味着该算法在最好和最坏情意味着该算法在最好和最坏情意味着该算法在最好和最坏情况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。况下的计算时间就一个常因子范围内而言是相同的。第20页/共197页五、算法分五、算法分类（按（按时间）多多项式式时间算法：凡可用算法：凡可用多多项式式来来对其其计算算时间界限的算法。界限的算法。指数指数时间算法：算法：计算算时间用用指数函数指数函数界限的算法。界限的算法。以下六种以下六种计算算时间的多的多项式式时间算法是最算法是最为
11、常常见的，其关的，其关系系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)指数指数时间算法一般有算法一般有O(2n)、O(n!)和和O(nn)等。其关系等。其关系为O(2n)O(n!)O(nn)第21页/共197页 注意：注意：注意：注意：当数据集的规模很大时，要在现代计算机上运当数据集的规模很大时，要在现代计算机上运行具有比行具有比O O（nlogn)nlogn)复杂度高的算法往往是很困难的。复杂度高的算法往往是很困难的。六、最好、最坏和平均情况六、最好、最坏和平均情况以以顺序序检索索为例例第22页/共197页第二章第二章 分治法分治法2.1 方法概述方法概述一、基本思
12、想一、基本思想1、设计思想：将整个思想：将整个问题分成若干个小分成若干个小问题后后,分而治之。分而治之。2、适用条件：、适用条件：问题规模很大；模很大；可以分成若干个与原可以分成若干个与原问题性性质相同的子相同的子问题，并可以，并可以分分别求解。求解。子子问题的解通的解通过整合可以得到原整合可以得到原问题的解。的解。3、设计方法：使用方法：使用递归策略。策略。第23页/共197页4、设计步步骤(1)分解：分解：将原将原问题分解分解为若干个相互独立、与原若干个相互独立、与原问题形式相同形式相同的子的子问题；(2)求解求解：若子：若子问题容易被解决容易被解决则直接解，否直接解，否则再再继续分解分解
13、为更更小的子小的子问题，直到容易解决；，直到容易解决；(3)合并合并：将已求解的各个子：将已求解的各个子问题的解，逐步合并以得到原的解，逐步合并以得到原问题的解。的解。第24页/共197页二、分治法的算法二、分治法的算法设计模式模式Divide-and-Conquer(n)/n为问题规模模1if n=n0/n0 为可解子可解子问题的的规模模2then 3 4 解子解子问题5 return(子子问题的解的解)64for i 1 to k/分解分解为k个子个子问题5 do yi Divide-and-Conquer(|Pi|)/递归解决解决Pi6 T MERGE(y1,y2,.,yk)/合并子合并
14、子问题7 return T递归过程程注意：分治法可以用注意：分治法可以用递归实现，也可以用循，也可以用循环实现。第25页/共197页 其中：其中其中：其中|P|表示表示问题P的的规模；模；n0为一一阈值，表示当，表示当问题P的的规模不超模不超过n0时，问题已容易直接解出，不必再已容易直接解出，不必再继续分解。算法分解。算法MERGE(y1,y2,.,yk)是是该分治法中的合分治法中的合并子算法，用于将并子算法，用于将P的子的子问题P1,P2,.,Pk的相的相应的解的解y1,y2,.,yk合并合并为P的解。的解。第26页/共197页时间复杂性分析时间复杂性分析时间复杂性分析时间复杂性分析：其中，
15、其中，T(n)是是输入入规模模为n的的Divide-and-Conquer的的时间，g(n)是是对足足够小的小的输入入规模能直接模能直接计算出答案算出答案的的时间，f(n)是是MERGE的的时间。倘若所分成的两个子倘若所分成的两个子问题的的输入入规模大致相等，模大致相等，则Divide-and-Conquer总的的计算算时间可以用下面的可以用下面的递推关系来表示：推关系来表示：(n足足够小小)(否否则)第27页/共197页2.2 二二 分分 检 索索一、一、问题描述描述已知一个按非降次序排列的元素表已知一个按非降次序排列的元素表a1,a2,an,要求判定要求判定某某给定元素定元素x是否在是否在
16、该表中出表中出现。若是，。若是，则找出找出x在表中的在表中的位置，并将此下位置，并将此下标值赋给变量量j；若非，；若非，则将将j置成置成0。二、二、问题分析分析设该问题用用I=(n,a1,a2,an,x)来表示，可以将它分解成来表示，可以将它分解成一些子一些子问题，一种可能的做法是，一种可能的做法是，选取一个下取一个下标k，由此得到三，由此得到三个子个子问题：I1=(k-1,a1,a2,ak-1,x),I2=(1,ak,x)和和I3=(n-k,ak+1,an,x)。第28页/共197页 对于于I2，通，通过比比较x和和ak容易得到解决。如果容易得到解决。如果x=ak,则j=k且不且不需再需再对
17、I1和和I3求解；否求解；否则，在，在I2 子子问题的的j=0，此，此时若若xak,只有只有I3留待求解，留待求解，在在I1子子问题中的中的j=0。在。在ak作了比作了比较之后，留待求解的之后，留待求解的问题（如果有的（如果有的话）可以再一次使用分治法来求解。如果）可以再一次使用分治法来求解。如果对所求所求解的解的问题（或子（或子问题）所）所选的下的下标k都是其元素的中都是其元素的中间元素下元素下标（例如，（例如，对于于I，k=(n+1)/2）,则所所产生的算法就是通常所生的算法就是通常所说的二分的二分检索。索。第29页/共197页三、二分三、二分检索算法索算法算法算法2.3 二分二分检索索/
18、给定一个按非降次序排列的元素数定一个按非降次序排列的元素数组A(1:n),n1,判判 断断x是否出是否出现。若是，置。若是，置j，使得，使得x=A(j),若非，若非，j=0/BINSEARCH(A,n,x)1 low 12 high n 第30页/共197页3 while lowhigh，数，数组A中没有找到中没有找到x，返回，返回j04 do5 6 /取取处于于low和和high之之间的中的中间值7 if x=Amid/找到找到值为x的元素，的元素，mid即即为其下其下标，返回，返回mid8 thenreturn mid9 else if x Amid/如果如果x Amid，则x可能位于可能
19、位于low与与mid之之间，10 /否否则x可能位于可能位于mid与与high之之间11 then high mid-112 else low mid+113 14 retrun 0 非非递归形式形式第31页/共197页四、算法的四、算法的证明明假定在假定在A9中中顺序存放着以下序存放着以下9个元素：个元素：-15，-6，0，7，9，23，54，82，101。要求。要求检索下列索下列x的的值：101，-14和和82是是否在否在A中出中出现。X=101low high midX=-14low high midX=82low high mid1951951956971426978981119992
20、1找不到898找到找到第32页/共197页A（1）（2）（3）（4）（5）（6）（7）（8）（9）元素-15-6079235482101比较次数323413234从算法中可以看到从算法中可以看到,所有的运算基本上都是所有的运算基本上都是进行比行比较和数和数据据传送，前两条是送，前两条是赋值语句句,频率率计数均数均为1。在。在while循循环中，中，我我们集中考集中考虑循循环的次数，而其他运算的的次数，而其他运算的频率率计数数显然与然与这些元素比些元素比较运算的运算的频率率计数具有相同的数量数具有相同的数量级，找到，找到这九个九个元素中的每一个所需的元素循元素中的每一个所需的元素循环的次数如下：
21、的次数如下：第33页/共197页五、时间复杂性分析五、时间复杂性分析五、时间复杂性分析五、时间复杂性分析 (1)(log n)(log n)(log n)(log n)(log n)第34页/共197页 分析：分析：对于于A中的中的n个数，如果个数，如果x在在A中出中出现，则是成功是成功检索，所索，所以成功以成功检索共有索共有n种情况，而不成功的种情况，而不成功的检索，索，x将取将取n+1个区个区间中的中的不同不同值，因此在，因此在计算出算出x在在这2n+1种情况下的种情况下的执行行时间后，就可以后，就可以求出其在各种情况下的求出其在各种情况下的时间复复杂性了。性了。例子：例子：A：（1）（2
22、）（3）（4）（5）（6）（7）（8）（9）元素：元素：-15 -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次，而其余的情况要比较次，而其余
23、的情况要比较4次，因此一次，因此一次不成功检索的元素平均比较次数就是次不成功检索的元素平均比较次数就是（3+3+3+4+4+3+3+3+4+4）/10=3.4。由于算法的执行过程实质上是由于算法的执行过程实质上是由于算法的执行过程实质上是由于算法的执行过程实质上是x x与一系列中间元素与一系列中间元素与一系列中间元素与一系列中间元素A A（midmid）的）的）的）的比较过程，所以可以用一个二元比较树来描述比较过程，所以可以用一个二元比较树来描述比较过程，所以可以用一个二元比较树来描述比较过程，所以可以用一个二元比较树来描述。第36页/共197页二元比较树：二元比较树：二元比较树：二元比较树：
24、（1）此树的结点由此树的结点由内结点和外结点内结点和外结点组成；组成；（2）每个内结点表示一次元素比较，用）每个内结点表示一次元素比较，用圆形结点圆形结点表示，在表示，在以元素比较为基础的二分检索中，每个内结点存放一个以元素比较为基础的二分检索中，每个内结点存放一个mid值；值；（3）外结点用外结点用方形结点方形结点表示，在二分检索中它表示一次不表示，在二分检索中它表示一次不成功的检索；成功的检索；（4）x如果在如果在A 中出现，则算法就在一个圆形结点处结束，中出现，则算法就在一个圆形结点处结束，该结点将指出该结点将指出x在在A中的下标；中的下标；x如果不在如果不在A 中出现，则算法中出现，则
25、算法就在一个方形结点处结束，如图所示。就在一个方形结点处结束，如图所示。第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个个结点描述点描述BINSRCH执行行过程的二元比程的二元比较树，所有成功所有成功检索都在内部索都在内部结点点处结束，而所有不成功的束，而所有不成功的检索都索都在外部在外部结点点处结束束。由于。由于2k-1n2k，因此所有的内部，因此所有的内部结点在点在1，2，3，k级，而所有的外部，而所有
26、的外部结点在点在k,k+1级（注意：根（注意：根在在1 级）。即是，成功）。即是，成功检索在索在i级终止所需要的元素比止所需要的元素比较次数次数是是i,而而不成功不成功检索在索在i级外部外部结点点终止的元素比止的元素比较数是数是i-1.因此因此定理得定理得证。定理定理2.1 若若n在区域在区域2k-1,2k)中，中，则对于一次成功的于一次成功的检索，索，BINSRCH 至多作至多作k次比次比较，而，而对于一次不成功的于一次不成功的检索，或者作索，或者作k-1次比次比较或者作或者作k次比次比较。第39页/共197页 由此：最坏情况下的成功由此：最坏情况下的成功检索和不成功索和不成功检索的索的计算
27、算时间是是（logn）,最好情况下的成功最好情况下的成功检索在根索在根结点点处到达，到达，时间是是（1），），而最好情况的不成功而最好情况的不成功检索要索要logn次元素比次元素比较，所以，所以时间是是（logn）。由于外部。由于外部节点都在点都在k和和k+1级，因此，每，因此，每种不成功种不成功检索的索的时间都是都是（logn），），故平均情况下不成功故平均情况下不成功检索的索的计算算时间是是（logn）。第40页/共197页 E=I+2n (1)令令S(n)是成功是成功检索的平均比索的平均比较数，数，则S（n)=I/n+1 (2)平均情况下成功平均情况下成功检索的索的时间复复杂性分析：性分
28、析：设根到所有内部根到所有内部结点的距离之和称点的距离之和称为内部路径内部路径长度度I，由，由根到所有外部根到所有外部结点的距离之和称点的距离之和称为外部路径外部路径长度度E，可以，可以证明：明：为什么要什么要+1第41页/共197页 令令U（n)是不成功是不成功检索的平均情况比索的平均情况比较数，而任何一个外数，而任何一个外部部结点所需要的比点所需要的比较数是由根到数是由根到该结点路径的点路径的长度，由此度，由此得：得：U(n)=E/(n+1)(3)利用（利用（1）-（3）可以得到：）可以得到：S(n)=(1+1/n)U(n)-1因此：平均情况下成功因此：平均情况下成功检索的索的时间复复杂性
29、性为：(log n)。第42页/共197页五、一种二分五、一种二分检索的索的变形形BINSEARCH1。BINSEARCH1的的while循循环中中x和和Amid之之间只用作一次比只用作一次比较。BINSEARCH1(A,n,x,j)1 low 12 high n+13 while low high4do56 mid(low+high)/27 if(x Amid)/在循环中只比较一次8 then high mid9else lowmid10 11 if x=Alow12 then j low/x出现13 else j=0 /x不出现14 return j第43页/共197页 BINSEARCH
30、和和BINSEARCH1相比相比较可看出，可看出，对于任何于任何一种成功的一种成功的检索，索，BINSEARCH1平均要比平均要比BINSEARCH多多作作次比次比较。BINSEARCH1的最好、平均和最坏的最好、平均和最坏情况情况时间对于成功和不成功的于成功和不成功的检索都是索都是。第44页/共197页 六、以比六、以比较为基基础检索的索的时间下界下界 1.什么是以比什么是以比较为基基础的的检索算法索算法 检索一索一给定元素定元素x是否在是否在A中出中出现。如果只允。如果只允许进行元素行元素间的比的比较而不允而不允许对它它们实施运算，在施运算，在这种条件下所种条件下所设计的的算法都称算法都称
31、为是以比是以比较为基基础的算法的算法。2.二分二分检索是以比索是以比较为基基础的的检索算法中最坏情况下的最索算法中最坏情况下的最优算法算法.第45页/共197页 定理定理2.3 设A（1：n）含有）含有n个不同的元素，个不同的元素，n1，它，它们被被排序排序为A(1)A(2)A(n)。又。又设用以比用以比较为基基础去判断去判断是否是否x A（1：n）的任何算法在最坏情况下所需的最小比）的任何算法在最坏情况下所需的最小比较次数是次数是FIND（n），那么），那么FIND（n）第46页/共197页 结论：由于二分由于二分检索所索所产生的比生的比较树中所有的外部中所有的外部结点都在点都在相相邻接的两
32、个接的两个级上上，不不难证明明这样的二元的二元树使得由根到使得由根到结点的最点的最长路径减至最小，因此，路径减至最小，因此，二分二分检索是解决索是解决检索索问题在最坏情况下的最在最坏情况下的最优算法。算法。证明：通明：通过考考虑模模拟求解求解检索索问题的各种算法的比的各种算法的比较树可可知，知，FIND（n）不大于）不大于树中根到一个叶子最中根到一个叶子最长路径的距离。路径的距离。在在这所有的所有的树中都必定有中都必定有n个内个内结点与点与x在在A中可能的中可能的n种出种出现相相对应，如果一棵二元，如果一棵二元树的所有内的所有内结点所在的点所在的级数小于数小于级数数k，则最多有最多有2k-1个
33、内个内结点，因此点，因此n 2k-1,即即FIND（n）=k 第47页/共197页一、直接求最大、最小元素一、直接求最大、最小元素算法算法2.5 直接找最大和最小元素直接找最大和最小元素maxmin(A,n)/将将A(1:n)中的最大元素置于中的最大元素置于max，最小元素置于，最小元素置于min/1 max A12 min A1;3 for i 2 to n4 do5 6 if max Ai 7 then min Ai8 2.3 找最大和最小元素找最大和最小元素 第48页/共197页时间复复杂性分析：性分析：STRAITMAXMIN在最好、平均和最坏情况下均需要作在最好、平均和最坏情况下均需
34、要作2(n-1)次元素比次元素比较。第49页/共197页如果稍做修改：如果稍做修改：用下面的用下面的语句代替句代替for循循环中的中的语句：句：if A(i)max then maxA(i)else if A(i)min then minA(i)endif endif 最好情况将在元素按最好情况将在元素按递增次序排列增次序排列时出出现，元素比，元素比较数数是是n-1；最坏情况将在；最坏情况将在递减次序减次序时出出现，元素比，元素比较是是2（n-1）；至于在平均情况下）；至于在平均情况下,A(i)将有一半的将有一半的时间比比max大，因此平均比大，因此平均比较数是数是3/2(n-1)。第50页/
35、共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)。如如果果()和和（）是是中中的的最最大大和和最最小小元元素素，则（）等等于于（）和和（）中中的的大大者者，（）等等于于（）和和（）中中的的小小者者。如如果果只只包包含含一一个个元元素，素，则不需要作任何分割直接就可得到其解。不需要作任何分割直接就
36、可得到其解。第51页/共197页2.算法算法算法算法.递归求取最大和最小元素求取最大和最小元素float An;maxmin（i,j,fmax,fmin）/最大和最小元素最大和最小元素赋给fmax和和fmin1 if i=j 2 then3 4 fmax Ai;5 fmin Ai;6 第52页/共197页7 else if i=j-18 then if Ai rmax25 then fmax lmax;26 else fmax rmax27 if lmin rmin28 then fmin rmin;29 else fmin lmin;30 递归调用用第54页/共197页利用层次分析法分析此递
37、归调用过程。（要求掌握）利用层次分析法分析此递归调用过程。（要求掌握）利用层次分析法分析此递归调用过程。（要求掌握）利用层次分析法分析此递归调用过程。（要求掌握）考考虑如下例子：如下例子：A：（：（1）（2）（3）（4）（5）（6）（7）（8）（9）22 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?第5
38、6页/共197页讨论：以上算法是否是最：以上算法是否是最优的？的？1）递归带来的来的额外的空外的空间开开销。2）当元素当元素A(i)和和A(j)的比的比较时间i和和j的比的比较时间相差不大相差不大时，过程程maxmin并不可取。并不可取。因此：当因此：当n是的是的幂时，3n/2-2是最好，平均及最坏情况的比是最好，平均及最坏情况的比较数数,和直接算法的比和直接算法的比较数数n相比，它少了。相比，它少了。可以可以证明，任何一种以元素比明，任何一种以元素比较为基基础的找最大和最小元素的找最大和最小元素的算法，其元素比的算法，其元素比较下界均下界均为 次。次。第57页/共197页 为说明明问题，假，
39、假设元素比元素比较与与i和和j间的比的比较时间相同，又相同，又设maxmin的的频率率计数数为C(n)，n=2k，,k是某个正整数，并且是某个正整数，并且对前两种情况，用前两种情况，用ij-1来代替来代替i=j和和i=j-1这两次比两次比较，这样，只用只用对i和和j-1作一次比作一次比较就足以就足以实现被修改被修改过的的语句。于是句。于是maxmin频率率计数数C(n)=n=2 n2?第58页/共197页解此关系式可得解此关系式可得C(n)=2C(n/2)+3=4C(n/4)+6+3 =2k-1C(2)+=2k+3*2k-1-3 =5n/2-3分分析析：STRAITMAXMIN的的比比较数数是
40、是3(n-1)(包包括括实现for循循环所所要要的的比比较)。尽尽管管它它比比5n/2-3大大些些，但但由由于于递归算算法法中中i，j，fmax，fmin进出出栈所所带来来的的开开销，因因此此maxmin在在这种种情情况下反而比况下反而比STRAITMAXMIN还要慢些。要慢些。第59页/共197页 根根根根据据据据以以以以上上上上分分分分析析析析可可可可以以以以得得得得出出出出结结结结论论论论：如如如如果果果果A A A A的的的的元元元元素素素素间间间间的的的的比比比比较较较较远远远远比比比比整整整整数数数数变变变变量量量量的的的的比比比比较较较较代代代代价价价价昂昂昂昂贵贵贵贵，则则则则
41、分分分分治治治治方方方方法法法法产产产产生生生生效效效效率率率率较较较较高高高高（实实实实际际际际上上上上是是是是最最最最优优优优）的的的的算算算算法法法法；反反反反之之之之，就就就就得得得得到到到到一一一一个个个个效效效效率率率率较较较较低低低低的的的的程程程程序序序序。因因因因此此此此，分分分分治治治治策策策策略略略略只只只只能能能能看看看看成成成成是是是是一一一一个个个个较较较较好好好好的的的的然然然然而而而而并并并并不不不不总总总总是是是是能成功的算法设计指导。能成功的算法设计指导。能成功的算法设计指导。能成功的算法设计指导。第60页/共197页2.4斯特拉森矩斯特拉森矩阵乘法乘法一、
42、一般的矩一、一般的矩阵乘法乘法设C=A*B,则利用常利用常规方法方法计算，所需算，所需时间是是二、二、分治法分治法求矩求矩阵乘法乘法 设n=2k，则可以将两个矩可以将两个矩阵的乘法做如下划分：的乘法做如下划分：第61页/共197页其中：其中：C11=A11B11+A12B21 C12=A11B12+A12B21 C21=A21B11+A22B21 C22=A21B12+A22B22可以可以证明明:C=AB=第62页/共197页三三.斯特拉森矩斯特拉森矩阵乘法乘法 斯特拉森矩斯特拉森矩阵乘法的乘法的设计思想思想:增加加法的次数增加加法的次数,减少乘减少乘法的次数法的次数.如果分如果分块矩矩阵的的
43、级大于大于2,则可以可以继续将将这些子矩些子矩阵分成更分成更小的方小的方阵,直至每个方直至每个方阵只含有一个元素只含有一个元素,以至可以直接以至可以直接计算算其乘其乘积.时间复复杂性分析性分析:n 2 n2则T(n)=O(n3)第63页/共197页先用七个乘法和十个加（减）法来算出以下的先用七个乘法和十个加（减）法来算出以下的P-VP=(A11+A22)(B11+B22)，Q=(A21+A22)B11R=A11(B12-B22)，S=A22(B21-B11)T=(A11+A12)B22，U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)然后用然后用8个加减法算出个
44、加减法算出这些些 Cij C11=P+S-T+VC12=R+TC21=Q+SC22=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)第65页/共197页因因为：7logn=nlog7 cn2(7/4)logn=cnlog4*nlog7
45、-log4=cnlog4+log7-log4=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
46、7次是必须的，这一方面改进只能从更高维数如次是必须的，这一方面改进只能从更高维数如3*33*3，或，或4*44*4并用递归分治的合并方法来实现，现在可以达并用递归分治的合并方法来实现，现在可以达到到o(no(n2.4953642.495364).).第67页/共197页一、基本方法一、基本方法1例子：例子：背背包包问题：已已知知有有n种种物物品品和和一一个个容容量量大大小小为M的的背背包包，每每种种物物品品i的的容容量量为wi。假假定定将将物物品品i的的一一部部分分xi放放入入背背包包就就会会得得到到pixi的的效效益益，这里里，0 xi1，pi0。采采用用怎怎样的的装装包包方方法法才才会会使
47、使装装入入背背包包物物品品的的总效效益益最最大大呢呢？显然然，由由于于背背包包容容量量是是M，因因此此，要要求求所所有有选中中要要装装入入背背包包的的物物品品总容容量量不不得得超超过M。如如果果这n件件物物品品的的总容容量量不不超超过M，则把所有物品装入背包自然把所有物品装入背包自然获得最大效益。得最大效益。如果如果这些物品容量的和大于些物品容量的和大于M，则在在这种情况下种情况下该如何装包呢？如何装包呢？第三章贪心方法第三章贪心方法31方法概述方法概述第68页/共197页例例:考考虑虑下下列列情情况况下下的的背背包包问问题题：n=3n=3，M M2020，(25(25，2424，1515）,
48、=(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.5在这些可行解中，如何得到最优解，正是贪心方法要解决的问题。在这些可行解中，如何得到最优解，正是贪心方法要解决的问题。在这些可行解中，如何得到最优解，正是贪心方法要解决的问题。在这些可行解中，如何得到最优解，正是贪心方法要解决的问题。第69页/共19
49、7页2 2、适用条件：适用条件：（1 1）有）有n n个输入；个输入；（2 2）它的解就由这）它的解就由这n n个输入的个输入的某个子集某个子集组成；组成；（3 3）这个子集必须满足一定的约束条件）这个子集必须满足一定的约束条件-可行解；可行解；（4 4）可可行行解解一一般般不不止止一一个个，但但是是要要要要求求求求的的的的是是是是最最最最优优优优解解解解即即即即使使使使目目目目标标标标函函函函数取得极值的解。数取得极值的解。数取得极值的解。数取得极值的解。第70页/共197页3 3有关概念有关概念（1 1）约束条件：约束条件：约束条件：约束条件：把子集必须满足的基本条件称为约束条件。把子集必
50、须满足的基本条件称为约束条件。（2 2）可行解可行解可行解可行解：把满足约束条件的子集称为该问题的可行解。：把满足约束条件的子集称为该问题的可行解。（3 3）目标函数：目标函数：目标函数：目标函数：（可行解一般来说是不唯一的）为了衡量可（可行解一般来说是不唯一的）为了衡量可行解的优劣，事先也给出了一定的标准，这些标准一般以用函行解的优劣，事先也给出了一定的标准，这些标准一般以用函数形式给出，这些函数称为目标函数。数形式给出，这些函数称为目标函数。（4 4）最优解：最优解：最优解：最优解：那些使目标函数取极值（极大或极小）的可行那些使目标函数取极值（极大或极小）的可行解，称为最优解解，称为最优解