《南开大学算法导论第五章》由会员分享，可在线阅读，更多相关《南开大学算法导论第五章（97页珍藏版）》请在金锄头文库上搜索。
1、1 第五章 分治策略 苏 明 2 分治策略 ?“分而治之” ?把一个问题分解成几个部分 ?递归解决规模比较小的类似问题 ?把子问题的解合成完整的解 3 分治策略 ?经常使用的办法： ?把一个规模为n的问题分解成两个规模n 的问题； ?分别递归解决两个部分的问题； ?在线性时间内把这两个部分问题的解合 成一个完整的解。 4 归并排序算法 ?问题：给定n个元素，按照递增的顺序对 其进行排序。 ?排序应用场景排序应用场景： ?直接应用： 目录文件排序； 电话簿排序； Google上输出按照 PageRank排序； 间接应用： 区间调度； 最小生成树问题； 数据压缩； 5 归并排序 ?归并排序 ?Di
2、vide array into two halves. ?Recursively sort each half. ?Merge two halves to make sorted whole. Jon von Neumann (1945) merge sort divide ALGORITHMS ALGORITHMS AGLORHIMST AGHILMORSTO(n) 2T(n/2) O(1) 6 归并排序 ?合并：把两个排好序的部分合成一个完整 的排序 ?效率分析：采用一个临时数组；需要O(n) 次比较 AGLORHIMST AGHI 7 归并排序 ?对于归并排序算法，设T(n)表示该算法
3、在规模为n的输入实例上最坏的运行 （比较）时间。 ?开始假设n是2的整数次幂 ?可以得到递归公式如下： 8 递推关系 ?命题5.1 对某个常数c, ?或者 = + 2, 2,)2/(2 )( nc ncnnT nT T(n) 0if n =1 Tn/2 () solve left half 1 2 4 3 4 +Tn/2 () solve right half 1 2 4 3 4 +n merging otherwise 9 递推关系 T(n) T(n/2)T(n/2) T(n/4)T(n/4)T(n/4)T(n/4) T(2)T(2)T(2)T(2)T(2)T(2)T(2)T(2) n lo
4、g2n 2(n/2) 4(n/4) . . . 2k (n / 2k)T(n / 2k) . . . n/2 (2) n log2n 10 递推关系 ?为了严格证明这个命题，先考虑最特殊 情形 ?命题：如果T(n)满足如下关系，且n是2 的整数次幂，那么T(n) = n log2n. T(n) = 0if n =1 2T(n/2) sorting both halves 1 2 4 3 4 +n merging otherwise 11 递推关系 ?证明：对于n1,可以得到 T(n) n = 2T(n/2) n + 1 = T(n/2) n/2 + 1 = T(n/4) n/4 + 1 + 1
5、 L = T(n/n) n/n + 1 +L+ 1 log2n 1 2 4 3 4 =log2n 12 递推关系 ?证明： 用归纳法也可以： ?n=1 命题显然成立； ?假设T(n) = n log2n成立( )，那么 T(2n)=2T(n) + 2n =2nlog2n + 2n =2n log2(2n)1() + 2n =2nlog2(2n) 所以命题对于成立。 k n2= 1 2 + = k n 13 递推关系 ?回到一般情形 ?命题：如果T(n)满足如下关系，那么T(n) n lg n. T(n) 0if n =1 Tn/2 () solve left half 1 2 4 3 4 +
6、Tn/2 () solve right half 1 2 4 3 4 +n merging otherwise 14 递推关系 ?证明：采用归纳法。 15 递推关系 ?采用部分替换的方法 在这种替换中，先猜想出解的形式，但 是开始的时候常数项以及相关的参数不 确定；在随后的推导中可以确定这些参 数的值。有点类似于“待定系数法”。 16 其他递推关系 ?命题5.3 对某个常数c， = + 2, 2,)2/( )( nc ncnnqT nT q2, q=1, q=2 递推关系的性质不同 17 其他递推关系 cn (3/2) cn (9/4)cn . . . cn/2 cn/4cn/4cn/4 cn
7、/2 cn/4cn/4cn/4 cn/2 cn/4cn/4cn/4 . . . q=3 18 其他递推关系 类似的根据上图可以得到： = = = = 1log 0 log1log 0 222 1 1 22 )( n j n j n j j r r cn q cncn q nT )( 1111 2222 2 loglogloglog log qqrn n nOn r c nn r c rn r c r r cn= = = = 定理5.4 任何满足5.3并具有q2的函数T(.)是 有界的。 )( 2 log q nO 19 其他递推关系 ?定理5.5 任何满足5.3式并具有q=1的函 数T(.)
8、(T(n)+ 2, 2,)2/(2 )( 2 nc ncnnT nT )()( 2 nOnT= 21 5.3 计数逆序 ?问题提出 ?Web网站使用一种称为协同过滤的技术， 试图使用这种技术把你(对于书，电影， 餐馆等)的爱好与其他人表现的爱好进行 匹配，一旦web网站识别某些人与你有 “类似”的口味（基于评价各种事物的比 较），它就推荐一些相关的新事物。 22 计数逆序 ?相似度量? ?考虑逆序逆序的个数 ?两个指标iaj. Songs You Me 14325 13245 ABCDE Inversions 3-2, 4-2 23 计数逆序 2 4 1 3 5 1 234 5 逆序数：3-(
9、2,1),(4,1),(4,3) 24 计数逆序 ?穷举（Brute force）: (n2). ?排序： (nlgn) ?？分治策略 -可同时进行逆序计数的工作 25 例子 ?如下给定的序列进行排序，计数逆序 Divide: O(1). 145810261291137 145810261291137 蓝色部分的逆序数？绿色部分的逆序数？ 26 例子 Divide: O(1). 145810261291137 145810261291137Conquer: 2T(n / 2) 5 blue-blue inversions8 green-green inversions 5-4, 5-2, 4-
10、2, 8-2, 10-26-3, 9-3, 9-7, 12-3, 12-7, 12-11, 11-3, 11-7 27 例子 ?分治策略 ?划分：把序列一分为二 ； ?分别递归求出左右各自部分的逆序数； ?组合: 计数左右部份之间的逆序数, 返回总的逆序数. Divide: O(1). 145810261291137 145810261291137Conquer: 2T(n / 2) 5 blue-blue inversions8 green-green inversions 9 blue-green inversions 5-3, 4-3, 8-6, 8-3, 8-7, 10-6, 10-9
11、, 10-3, 10-7 Total = 5 + 8 + 9 = 22. Efficient Combine: ? 28 例子 组合: 计数蓝-绿逆序，假设左右部分已 经排序 假设左右部分已 经排序，合并这两个部分为完整的排序。 310714181916172325211 632200 13 blue-green inversions: 6 + 3 + 2 + 2 + 0 + 0 Count: O(n) 273101114161817192325Merge: O(n) T(n) Tn/2()+Tn/2()+ O(n) T(n)= O(nlogn) 29 算法 Merge-and-Count(A
12、,B) 维护一个Current指针指向每个表，初始化指向首元素 维护一个变量Count用于逆序的计数，初始为0 While两个表都不空 令ai与bj是由Current指针指向的元素 把这两个表中较小的元素加到输出表中 If bj是较小的元素 then 把Count加上在A中剩余的元素数 Endif 把较小元素选出的表中的Current指针前移 Endwhile 一旦一个表为空，把另一个表剩余的所有元素加到输出中 返回Count和合并后的表 30 算法 Sort-and-Count(L) If这个表中有一个元素，then 没有逆序 Else 把这个表划分成两半， A包含前个元素 B包含剩下的个元
13、素 (rA,A)=Sort-and-Count(A) (rB,B)=Sort-and-Count(B) (r,L)=Merge-and-Count(A,B) Endif 返回r=rA+rB+r以及排好序的表L 2/n 2/n 31 算法分析 ?定理5.7 Sort-and-Count算法正确对输入 表排序并且计数逆序个数；它对具有n个 元素的表运行在O(nlogn)时间。 32 5.4 最邻近点对 ?问题：给定平面上的n个点，找最邻近的 一对点 ?计算几何领域的基础 ?20世纪70年代， M. I. Shamos, D. Hoey, 关心是否能找到一个渐进的比平方阶更 快的算法 是否能找到一个
14、渐进的比平方阶更 快的算法 33 最邻近点对 ?应用领域 ?Graphics, computer vision, geographic information systems, molecular modeling, air traffic control. ?Special case of nearest neighbor, Euclidean MST, Voronoi. 34 最邻近点对 可行性可行性 ?特殊情形： 如果是所有的点在一个维度 的直线上： O(nlogn) ?为了使得后面的描述相对简单，假设这 些点的x坐标都不相同 35 例子 ?考虑一种划分：把一块平面区域分成四四个部分 L
15、 36 例子 ?这样的划分可能会带来的问题：不均匀 L 37 分治算法 ?划分的时候：用一条垂直线把点集分成 相等的两部分 L 38 分治算法 ?在左右半部分寻找各自最邻近的点对 12 21 L 39 分治算法 ?组合：在“交界”的边中寻找最近的点对 ?最后返回上面3个解中的最优解 12 21 8 L 40 分治算法 ?问题的关键在于：寻找“交界”的边中比 还要近的点对。 ),min( RL = 12 21 = min(12, 21) L 41 分治算法 ?于是根据平面几何的约束性质平面几何的约束性质，只需要 考虑分界线附近的点集情况。 12 21 L = min(12, 21) 42 分治算法 ?把“窄带”之中的点集按照y坐标的大小排 序编号 12 21 1 2 3 4 5 6 7 L = min(12, 21) 43 分治算法 ?定义 设si是2窄带中按照y坐标排序的 第i个点。 ?命题. 如果 |i j| 12, 那么si与sj之间 的距离至少是. ?证明. ?在的小盒子中，至多只有一个点. ?si与sj之间至少可以间隔两行，距离 2(). 44 分治算法 27 29 30 31 28 26 25 2 rows 39 i j 注意到这里目的是为了说 明不需要在窄带之间进行 两两之间点的比较；只需 要在一个常数阶的范围内 比较就可以。 比如12还可以
