课件递归与分治二

1、算法艺术与信息学竞赛标准课件递归与分治 ( 二)目录一、 Karatsuba 快速乘法二、 Strassen 矩阵乘法三、求解线性递推方程四、快速排序五、求 k 大元素六、最近点对问题Karatsuba 快速乘法一、给两个 n 位数 ,计算它们的乘积分析类似于 Strassen 矩阵乘法 ,先写成递归形式容易得到下面的过程 , T(n)=4T(n/2)+O(n),还是 T(n) = O(n2).因此Karatsuba 快速乘法Anatoli Karatsuba( 由Knuth 改进 ) 在 1962 年提出:ac + bd (a-b)(c-d) = bc+ad因此中间项次只需要次递归调用而不是

2、两分析显然 ,递归方程为 T(n)<=3T(n/2)+O(n),T(n) = O(nlg3) = O(n1.585),比 O(n2) 快.注意 :,真实应该使用二进制而不是 10 进制 ,特点这样可以充分利用乘法的进一步得 :更细的进行分治可以得到更好的算法 ,直到 Fast Fourier Transform,用它计算乘法只需要 O(nlogn) 的时间二、 Strassen 矩阵乘法标准算法基本分治算法基本分治算法分析Strassen 算法Strassen 算法Strassen 算法把A 和B 划分成 (n/2)*(n/2) 个子矩阵Divide:Conquer: 递归对子矩阵记性

3、7 次乘法Combine:对子矩阵进行加法和减法得到 C三、求解线性递推方程Fi= a1Fi-1+a2Fi-2+a3Fi-3+akFi-k已知 F1, F2, , Fk,求任意的 Fn例: Fibonacci 数数学通项公式(15 )n(15 )n22Fn5第二项小于 1 ，可以只算第一项，舍入由于到最近的整数可以用对数或倍增法问题：精度误差！代码 :直接递归可以直接写出递归代码int fib(int n)if(n < 2) return n;else return fib(n-1) + fib(n-2);分析记T(n) 为计算 fib(n) 的时间复杂度T(n)=T(n-1)+T(n-

4、2),设T(1)=T(2)=c,则T(n)=c*Fn-2.由于5 + 1fn+1limn= 1.618 .fn2因此 T(n) = O(1.618n),指数时间算法 !动态依次计算出很多结果 ,时间复杂度仅为 O(n),升到 O(n)采用预处理的方式但空间复杂度也上void precalc_fib(int n) f0 = 0; f1 = 1;for(int i = 2; i <= n; i+) fi = fi-1 + fi-2;滚动数组在执行的过程中计算出了 F1, F2, F3, Fn,但代价是使用了 O(n) 的空间存放这些数如果的确需要得到所有值 ,附加空间是必须的 ,但如果只需要

5、得到 Fn 呢?滚动数组 :掉滚动的含义 :把以后再也用不到的值及时扔在递推的过程中 ,数组内元素值始终发生变化代码 :滚动数组下面的代码 , F0.2 实际代表 Fi-2Fiint fib(int n)f1 = 0; f2 = 1;for(int i = 2; i <= n; i+) f0 = f1; f1 = f2; f2 = f1 + f0;return f2;分析一开始 f1=0, f2=1 实际上是 F0=0, F1=1第i 次循环时 ,刚开始 f0, f1, f2 保存着Fi-3Fi-1,执行以后变为了 Fi-2Fi问题 :如果递推式比较长，每次需要花费比较多的时间把数组进行

6、“移位” .维的情况下这个移位可能很慢！在多是用循环数组 ,让 fp 为比较好的解决当前要求的值，则 fprev(p) 和fprev(prev(p) 就是前两次求出的值代码 :循环滚动数组int fib(int n) int p=1;f0 = 0; f1 = 1;for(int i = 2; i <= n; i+) p = next(p);fp=fprev(p) + fprev(prev(p);return fp;矩阵乘法m*n 矩阵 A 和 n*p 矩阵 B 可以相乘得 m*p 的矩阵C Cik=sumAijBjk,其中 j 取遍 1,2,3,n矩阵乘法满足结合率 ,但不满换率和自然数

7、一样，可以用倍增法求矩阵的幂特别地，两个 2*2 矩阵相乘的公式为acbdegfhaecebgdgafcfbhdh分析注意到1110ababa如果让 a=Fk-1, b=Fk,我们就能得到 Fk与Fk+1从F0 和F1 出发 , 由结合律得 :NF111010N1FN可用倍增法在 O(logn) 时间内求出幂 ( 忽略高精度)一般情形LLLLO1fia1fia2 a1 10M0fia201M0akfi设12ka300MLak00M0Afififk1k1f kMf 0kMfi2iFAF2,若 F则i00四、快速排序一个基于分治思想的排序算法1962 年由 C.A.R.Hoare 提出原地排序，不

8、像归并排序需要辅助空间微调后非常实用快速排序的分治思想Divide.把数组以轴心 x 为分界线划分成两部分，x 小，右边的元素x 大，如下左边的元素图Conquer.Combine.递归把两部分排序平凡的关键：线性时间的划分过程划分过程一划分过程一划分过程二两个指针 left 和right. left 左边的x 小, rightx 大,右边的未知区域在中间left 和right 交替移动 ,一旦发现不满足要求的元素就停下来 .要求交换这两个元素 ,使同时满足好处：当相同元素比较多时较快划分过程二框架虽然效率还可以优化 ,但非常容易理解快速排序主过程不管使用哪种划分，快速排序的主过程如下：最坏情

9、况分析如果每次划分出来的序列都是一边 n-1 个元素一边 1 个元素解决方案：随机划分随机算法分析令 T(n) 为随机快速排序时间复杂度 .注意 T(n) 是一个随量，而不是一个确定值对于 k=0,1,n-1, 定义指示随random variable)量(indicator每种划分都是等概率的，因此 Xk的期望全是 1/n按定义展开根据数学期望的定义，我们有两边取期望，得计算期望第一步：期望的线性性质第二步： Xk 是随量第三步：期望的线性性质， Xk 的期望为 1/n简化后的递归式注意：前两项实际是相同的合并前两化简第三项，得常数 a>0 使得下面我们证明：ET(n)<=anl

10、gn首先证明下面数学归纳法用第二数学归纳法，则有取a 足够大，让 an/4 比(n) 大即可五、求 k 大元素给数组 A1.n ，找出第 k 大的元素问题 :显然可以先排序 ,但至少 O(nlogn) 的时间如果不排序 ,可以更快速的找到算法一示例分析和快速排序类似 ,需要求如下的期望注意到最后一步合并时 n/2 开始的元素才出现，其他元素不出现，因此有仍然使用数学归纳法，需要用到事实数学归纳法和快速排序类似让c 大到 cn/4 比(n) 大即可算法二刚才的算法是随机的，期望是线性是否最坏情况线性的顺序统计算法？是肯定的 .1973 年,由 Blum, Floyd, Pratt, Rivest

11、 和Tarjan 提出思想：选取好的 pivot ，然后执行划分并递归选择（和随机选择的不同点仅仅是由随机选pivot 改为了递归的确定性选pivot ）算法梗概步骤 1 、 2分析一共 n/5 个组， n/5 个”组中位数” ( 黄色 )所有“组中位数”的中位数为 x( 红色 )至少有 n/5/2=n/10 个”组中位数”比 x 小,而每个组的中位数比同组另两个数大，因此每组至少 3 个元素比 x 小,素比 x 小 .一共至少有 3*n/10 个元类似地，至少有 3*n/10 个元素比 x 大当 n>=50 时， 3*n/10>=n/4,即最坏的划分为1/4-3/4 划分。因此步

12、骤 4 需要的时间为 O(3n/4)时间复杂度分析数学归纳法使用数学归纳法即可，和前面类似六、最近点对问题给定平面上 n 个点的坐标 ,最近的两个点找出其中欧几枚举算法 :需要枚举 O(n2) 个点对 ,每个距离的计算时间为 O(1),有更好的算法吗 ?总 O(n2)分治法用分治法解决 .先按x 坐标排序 ,把所有点划分成个数尽量相等的两部分 ,距离为 dl 和dr.分别求最近点对 ,设合并令 d=mindl, dr,则两边的点对中，只有下面的竖条中的才有可能更近合并需要检查竖条里的所有点对吗 ?不需要 .从上往下看 ,对于任何一个 p,另一侧可能与它组成更近的点对在一个正方形中 ,它最多只有

13、 4 个点( 否则这个方格中会有距离比 d 小的点对 )最坏情况 ( 同一行的红蓝点几乎重合 ),接下来的 7 个点需要检查p伪代码r)Closest-Pair(P,l,if q dl dr d forrl<3thenreturnBrute-Force(P,l,r)(l+r)/2 Closest-Pair(P, Closest-Pair(P,l,q,q-1)r)min(dl,dr)iifltor doPq.x append-dPi.x SPq.x+dthenPitoSortforifSon y-coordinatej any1tosize_of(S)-1doofd(Sj,Sj+1), .

14、,d(Sj,Sj+7)issmallerthand,setdtothesmallestreturnd时间复杂度分析由于合并时要把竖条内的点按 y 坐标排序 ,合并是O(nlogn) 的递归方程 :因此if n3(n / 2)T(n)=O(nlog2n)n log notherwise下面把它优化到 O(nlogn)优化实现把所有点分别按 x 和y 排序放在两个有序表 x 表和 y 表Divide. 把点按 x 值分成两半后 ,按顺序遍历y 表,步 O(n)根据 x 值拆分成两个 y 表.这一Combine.合并得到拆分前的 y 表,同时这一把在竖条内的点提取出来扫描一遍 ,步 O(n)因此时间复杂度降为 O(nlogn)现详细描述对 y 表的两个操作拆分y 表x 表为 : (1, 3), (2, 2), (3, 4), (4, 1)y 表为 : (4, 1), (2, 2), (1, 3), (3, 4)根据 x 表,x>=3需把点分成两部分 : x<=2 和按顺序遍历y 表,出四个点应分别放在右边、左边、左边和右边 ,果为 左边