2、T(n/2)+f(n).其它g(n)n很小时，直接计算时间。f(n)分成二个子问题解后的整合时间。例1.1求一个集合中的最大元素和最小元素。Proceduremaxmin(s);1.if
3、s
4、=22.thenbegin设
5、s
6、={c,d};3.(a,b)←(MAX（c,d),MIN(c,d)).endelsebegin4.把S分成二个子集S1，S2，各存一半元素；5.(maxl,minl)←maxmin(S1);6.(max2,min2)←maxmin(S2);7.（a,b）←(MAX(max1,max2),MI
7、N(min1,min2))end例：1.2找第k个最小元素。一般先分类为递减序列，得到第k个最小元素，要O(nlogn).分治法可以O(n)内得到第k个最小元素。当k=[n/2]时，成为在线性时间内找一个序列的中值问题。17procedureSELECT(k,s)bagin.1.if
8、s
9、<50then2.begin3.把S分类4.returnS的第K个最小元素.end5.else6.begin7.把S划分成各为五个元素的[
10、s
11、/5]个子序列；8.设L是剩余元素（如果有的话）；9.把上述各5个元素序列分类；10
12、.设M是5个元素的中值序列；11.m←SELECT(Ñ
13、M
14、/2Ò,M)；12.设S1，S2，S3为S的分别<，=，>m的元素序列；13.if
15、S1
16、≥kthenreturnSELECT(k,S1)else14.if(
17、S1
18、+
19、S2
20、≥k)thenreturnm15.else16.returnSELECT(k-
21、S1
22、-
23、S2
24、,S3)endend说明：1.把S大问题化为S1，S2，S3三个小问题。2.选合适中值，原n变为[n/5]个数中选，速度就快5倍。至少有1/4的元素m,至少有1/4的元素m。3.子序列用
25、5分割是算法中有二个SELECT递归调用，每次是对r
26、s
27、的序列调用，二个序列之和必须<
28、s
29、的保证。每列为5个元素分类序列按分类次序列出的序列Mm[n/5]个已分类序列17Procedure(k,s)(类似快速分类)1.if
30、s
31、=12.thenreturnSelse3.begin4.随机地从S选出一个元素a;5.设S1，S2，S3分别为>，=，32、S1
33、≥kthenreturnSELECT(k,S1)else7.if
34、S1
35、+
36、S2
37、≥kthenreturn(a)8.else9.returnS
38、ELECT(k-
39、S1
40、-
41、S2
42、,S3)end一、贪心法问题：n个输入及一组约束条件。求：可行解---满足约束条件的任一输入子集。最优解---满足给定目标函数达到极大或极小的解。方法：①每步上考虑一个输入②根据某个优化测度（可以是目标函数），每一步上都保证获得局部最优解。③一步一步进行，直到可行解。注意：贪心法并不一定是最优解，但当一个问题复杂度很高时能用复杂度低得多的方法快速得到次优解也值得。例2.1背包（knapsack）问题。问题：n个物体（物体i的重量为wi，价值为pi）背包载荷能力m求：把物体i的Xi
43、部分(1in，0Xi1)装入背包中，使背包内所放物体的价值最高SPiXi且SWiXim例如n=3,m=20(p1,p2,p3)=(25,24,15)(w1,w2,w3)=(18,15,10)四种可行解（x1,x2,x3）∑WiXi∑PiXi1(1/2,1/3,1/4)16.524.252(1,1/15,0)20.028.23(0,2/3,1)20.031.04(0,1,1/2)20.031.5思路：把单位价值最高的先放入，物2，为24/15。放满15，余5把次价值再放入，物3，为15/10放10/2=5。所以此解
44、最优。17例2.1启发式算法设计方法1：贪心法解为启发式方法之一，是获取一个“好”的解的重要方法①②③④⑤①º20301011②15º14414③39º88④9618º17⑤761316º贪心法①④②③⑤①cost=43最优解①⑤②④③①cost=42所以直接用贪心法不一定为最佳。其它方案：1.选择不同起点，因为是一个圈，任意起点、各点都可以。2.交替地选用最小边和次小边
