算法分析与设计 第五讲 分治法及相关实例分析

《算法分析与设计 第五讲 分治法及相关实例分析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计第五讲分治法及相关实例分析1主要内容快速排序的改进Fibonacci数列Strassen矩阵乘法最大元、最小元最近点对问题2快速排序的分析QUICKSORT(A,p,r)ifp

2、A[r]returni+13快速排序的随机化版本主要区别在于主元的选择不总是选择A[r]作为主元，而是从A[p…r]中随机选择一个元素作为主元具体操作方法是将A[r]与A[p…r]中的随机选中的一个元素交换RANDOMIZED-PARTITION(A,p,r)1i←RANDOM(p,r)2exchangeA[r]↔A[i]3returnPARTITION(A,p,r)RANDOMIZED-QUICKSORT(A,p,r)1ifp

3、CKSORT(A,p,q-1)4RANDOMIZED-QUICKSORT(A,q+1,r)4快速排序的实际应用通常是用于排序的最佳实用选择原地排序，在虚存环境中也可以很好工作5Fibonacci数列1n0F(n)1n1F(n1)F(n2)n1n递归算法：(),(15)/2自底向上，依次计算Θ(n)有更好的方法吗？6Fibonacci数列矩阵法nFFnn111FFnn1107矩阵乘法矩阵乘法AaBbij,iji,j1,2,...,

4、nCABc[]ijncaijikbkjk18矩阵乘法直接解法fori←1tondoforj←1tondocij←0fork←1tondocij←cij+aikbkj时间复杂度3()n9矩阵乘法分治策略假设n为2的幂，将矩阵A，B和C中每一矩阵都分块成为4个大小相等的子矩阵，每个子矩阵都是n/2×n/2的方阵CC1112AABB11121112CC2122AABB21222122CAB10矩阵乘法分治策略分析2Tn()8(/2)Tn()n3Tn()()n

5、直接分治的时间复杂度并不比直接计算好11Strassen的策略只需要7次子矩阵的乘法引入M(i=1,2,…,7)，如下iCMMMMMA(BB)1154261111222CMMM(AA)B12122111222CMMM(AA)B21343212211CMMMMMA(BB)2251374222111M(AA)(BB)511221122M(AA)(BB)612222122M(AA)(BB)71121111212Strassen矩阵乘法分析2Tn()7(/2)Tn()n2

6、.81Tn()(n)更好的算法？2.376Tn()(n)13最大元、最小元给定n个数据元素，找出其中的最大元和最小元直接解法：逐个找，用n-1次比较来找出最大元，再用n-2次比较来找出最小元，比较次数（基本运算）为2n-3次可以用分治法吗？14最大元、最小元分治法当n=2时，一次比较就可以找出两个数据元素的最大元和最小元当n>2时，可以把n个数据元素分为大致相等的两半求数组最大元、最小元的算法下界3/22n15最近点对对于平面上给定的N个点，给出距离最近的两个点Bruteforce法：把所有点对逐

7、一检查一遍分治策略•如何分解？•如何合并？16最近点对点数较少时的情形YYY直接计算直接计算d=∞XXX只有一个点只有两个点只有三个点17最近点对分解对所有的点按照x坐标从小到大排序根据下标进行分割，使点集分成两个集合18最近点对解决递归寻找P和P中的最近点对LR设其找到的最近点对的距离分别是δ和δLR置δ=min(δ,δ)LR19最近点对合并可能并不是δ，存在这样的情况，一个点在P中，L另一个点在P中，而这两点之间的距离小于δR如何检查呢？只考虑分割线两侧距离各为δ的点继续压缩点的范围20最近点对难点

8、如何在线性时间内获得YYXXY,,,,LRLR21分治法小结二分搜索幂乘合并排序快速排序Fibonacci数列Strassen矩阵乘法最大元、最小元最近点对问题……22