三章Divide-and-Conquer技术.ppt
《三章Divide-and-Conquer技术.ppt》由会员分享,可在线阅读,更多相关《三章Divide-and-Conquer技术.ppt(36页珍藏版)》请在三一文库上搜索。
1、第三章第三章 Divide-and-Conquer Divide-and-Conquer 技术技术 邹权(博士)邹权(博士) 计算机科学系计算机科学系 3.1 3.1 Divide-and-Conquer原理原理 3.2 3.2 整数乘法整数乘法 3.33.3 矩阵乘法矩阵乘法 3.4 3.4 Finding the closest pair of pointsFinding the closest pair of points 提要提要 3.13.1 Divide-and-ConquerDivide-and-Conquer原理原理 Divide-and-ConquerDivide-and-C
2、onquer算法的设计算法的设计 Divide-and-ConquerDivide-and-Conquer算法的分析算法的分析 设计过程分为三个阶段设计过程分为三个阶段 DivideDivide: 整个问题划分为多个子问题整个问题划分为多个子问题 ConquerConquer:求解各子问题求解各子问题( (递归调用正设计的算递归调用正设计的算 法法) ) CombineCombine:合并子问题的解合并子问题的解, , 形成原始问题的解形成原始问题的解 Divide-and-ConquerDivide-and-Conquer算法的设计算法的设计 原始问题原始问题 求解子问题求解子问题 子问题子
3、问题子问题子问题子问题子问题 求解子问题求解子问题求解子问题求解子问题 子问题解子问题解子问题解子问题解子问题解子问题解 合并子解合并子解 问题分解问题分解 DivideDivide ConquerConquer MergeMerge 原始问题的解原始问题的解 Homework 云计算、Map-Reduce、Hadoop、Mahout 分析过程分析过程 建立递归方程建立递归方程 求解求解 递归方程的建立方法递归方程的建立方法 设输入大小为设输入大小为n,T(nn,T(n) )为时间复杂性为时间复杂性 当当n1if n1 使用使用MasterMaster定理定理 T(nT(n)=)=OO( (n
4、 nlog3 log3)=O( )=O(n n1.59 1.59 ) ) 算法的分析算法的分析 3. 3.3 3 矩阵乘法矩阵乘法 问题定义问题定义 输入输入:两个两个n n n n矩阵矩阵A A和和A A 输出输出:X X和和Y Y的积的积 通常,计算通常,计算XYXY的时间复杂性位的时间复杂性位O(nO(n 3 3 ) ), 我们给出一个复杂性为我们给出一个复杂性为O(nO(n2.81 2.81) )的算法。 的算法。 算法的数学基础算法的数学基础 l l 把把C=ABC=AB中每个矩阵分成大小相同的中每个矩阵分成大小相同的4 4个子矩阵个子矩阵 每个子矩阵都是一个每个子矩阵都是一个n/2
5、n/2 n/2n/2矩阵矩阵 l l 于是于是 = 展开并整理等式的右边,即得到计算的方法展开并整理等式的右边,即得到计算的方法 MM 1 1 = A= A11 11 (B (B12 12 - B - B22 22 ) ) MM 2 2 = (A= (A11 11 + A + A12 12) B ) B22 22 MM 3 3 = (A= (A21 21 + A + A22 22) B ) B11 11 MM 4 4 = A= A22 22 (B (B21 21 - B - B11 11 ) ) MM 5 5 = (A= (A11 11 + A + A22 22) (B ) (B11 11 +
6、 B + B22 22 ) ) MM 6 6 = (A= (A12 12 - A - A22 22) (B ) (B21 21 + B + B22 22 ) ) MM 7 7 = (A= (A11 11 - A - A12 12) (B ) (B11 11 + B + B12 12 ) ) 计算计算n/2n/2 n/2n/2矩阵的矩阵的1010个加减个加减和和7 7个乘法个乘法 算法算法 C C 11 11 = M = M 5 5 + M+ M 4 4 - M- M 2 2 + M+ M 6 6 C C 12 12 = M = M 1 1 + M+ M 2 2 C C 21 21 = M =
7、M 3 3 + M+ M 4 4 C C 22 22 = M= M 5 5 + M+ M 1 1 M M 3 3 M M 7 7 计算计算n/2n/2 n/2n/2矩阵的矩阵的8 8个加减个加减 1818个个n/2n/2 n/2n/2矩阵加减法,每个需矩阵加减法,每个需O(nO(n 2 2 ) ) 7 7个个n/2n/2 n/2n/2矩阵乘法矩阵乘法 建立递归方程建立递归方程 T(n)=O(1) n=2T(n)=O(1) n=2 T(n)=7T(n/2) + O(n T(n)=7T(n/2) + O(n 2 2 ) n2) n2 使用使用MasterMaster定理求解定理求解T(n)T(n)
8、 T(n) = O(nT(n) = O(nlog7 log7) ) O(n O(n2.81 2.81 ) ) 算法复杂性分析算法复杂性分析 3. 3.4 Finding the closest 4 Finding the closest pair of pointspair of points 问题定义问题定义 输入输入:EuclideanEuclidean空间上的空间上的n n个点的集合个点的集合QQ 输出输出:P P 1 1 , P, P 2 2 Q Q, , Dis(Dis(P P 1 1 , P, P 2 2 )=)=MinDis(MinDis(X X, Y, Y) | ) | X,
9、YX, Y QQ Dis(Dis(X X, Y, Y) )是是EuclideanEuclidean距离距离: : 如果如果X=(X=(x x 1 1 , x, x 2 2 ), Y=(), Y=(y y 1 1 , y, y 2 2 ) ),则,则 一维一维空间算法空间算法 利用排序的算法利用排序的算法 算法算法 把把QQ中的点排序中的点排序 通过排序集合的线性扫描找出最近点通过排序集合的线性扫描找出最近点 对对 时间复杂性时间复杂性 T(T(n n)=)=O(O(n nloglogn n) ) 一维空间算法一维空间算法( (续续) ) Divide-and-conquerDivide-and
10、-conquer算法算法 Preprocessing:Preprocessing: 1.1. 如果如果Q Q中仅包含中仅包含2 2个点,则返回这个点对个点,则返回这个点对; 2.2. 求求Q Q中点的中位数中点的中位数mm。 Divide:Divide: 1. 1. 用用QQ中点坐标中位数中点坐标中位数mm把把Q Q划分为两个划分为两个 大小相等的子集合大小相等的子集合 Q Q 1 1 = = x x Q Q | | x x mm, , Q Q 2 2 = = x x Q Q | | x x mm Q Q1 1 Q Q2 2 p p1 1 p p2 2 p p3 3 q q3 3 q q2 2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Divide and Conquer 技术
链接地址:https://www.31doc.com/p-2625818.html