算法设计与分析-递归与分治

第2章 递归与分治策略

学习要点:

理解递归的概念。 掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。

(1)二分搜索技术；(2)大整数乘法； (3)Strassen矩阵乘法； (4)棋盘覆盖；

(5)合并排序和快速排序；(6)线性时间选择； (7)最接近点对问题； (8)循环赛日程表。

学习如何求解递归式这对于分析递归算法 非常有用，主要有5种方法求解递归式。 1.代换法 2.递归树法 3.主方法 4.生成函数法 5.特征方程根

1.代换法求解递归式1.猜答案(可以不需要知道常数系数确切是 多少，仅需要猜它的形式，如n2 ,再试图 解出它的常数。即先推测递归方程的显式 解) 2.数学归纳法验证递归式。验证是否这个递 归式，按照数学归纳法满足条件。即用数 学归纳法证明推测的正确性。 3.找出常数。

例1:T(n)=4T(n/2)+n; T(1)=1; 1.猜T(n)=O ( n3 );想办法证明T(n)≤c * n 3 2.假设T(k ) ≤c k3 ( k=n/2)即对k满足T(n)=O ( n3 ),即有T(n/2 ) ≤c (n/2)3 T(n)=4T(n/2)+n (对T(n/2)即对k+1看是否满足假设) ≤4c (n/2) 3 +n = c/2* n 3 +n = c * n 3 –(c/2* n 3 – n ) ≤c*n3 (c/2* n 3 – n ≥0,即只要c ≥2就可以) 因此递归式的上界是O ( n3 );

例1:T(n)=4T(n/2)+n; T(1)= θ (1 ); 1.猜T(n)=O ( n2 );根据符号O的定义，对n>n0, 有T(n) ≤ c n2 2.假设T(k ) ≤c k2 ( k<n ) 把这个解代入递归方程，得到 T(n)=4T(n/2)+n ≤4c (n/2) 2 +n = c* n 2 +n = c * n 2 –(–n)而–n不是一个正数，无法得出c * n 2 –(–n) ≤ c * n 2

但假定归纳假设条件为： T(k ) ≤c1k2 -c2 k ( k<n ) 这里减去c2 k ,因其是 低阶项，不会影响到n足够大时的渐近性), 因此T(n)=4T(n/2)+n ≤ 4(c1 (n/2) 2 -c2 (n/2) )+n = c1n2 +n - 2c2 n = c1n2 - c2 n -(c2 n - n) ≤ c1n2 - c2 n (要满足条件 c2 n – n ≥0, 即只要 c2 –1 ≥0,即c2 ≥ 1即可) 即T(k ) ≤c k2 -c k ,对任意的c 1 2 1, c2 ≥ 1成立；

但必须注意c1要足够大，因为： 基本情况T(1) ≤c1 - c2 而T(1)= θ (1 )即T(1)是常数，我们需要选 择c1 ,至少比c2大，而c2 ≥ 1,因此c1要足 够大。 如何求出下界，解决办法之一是假设T(k ) ≥ c1k2 -c2 k ( k<n ),其余步骤类似。

因此递归式的上界是O ( n2 );

练习1:T(n)=4T(n/2)+n; T(1)= θ (1 ); 1.猜T(n)=O ( nlogn );

代换法求解递归式需要先猜出答案大概是 多少，这比较困难。

2.递归树法

递归树法不严谨，但很直观，让你知道答 案大概是多少。一般我们可以用这种方法 求出答案，然后用代换法验证其正确性。

例1:T(n)=2T(n/2)+n; n n/2 n/2 n/4 n/4 n/4 n/4 ……………….. 1 1 1 ….. 11 树的高度是logn,叶节点的个数是n,用递归树求 解递归式就是将每层的复杂度加起来。如第一层 是n,第二层是n/2 + n/2 =n,第三层是n/4 + n/4 + n/4 + n/4 =n…..最后一层(即logn层)是 1+1+…+1=n; 第一层+第二层+第三层+…+最后一层=nlogn。 T(n)=2T(n/2)+n的渐进复杂度是O(nlogn)

例:2:T(n)= T(n/4)+ T(n/2)+n2 即假设有个算法，问题的规模为n,先四等 分地递归，再二等分地递归，再做一个非 递归的n2复杂度的工作。下面用树的形式展 开递归。

T(n)=n2 T(n/4) T(n/2)

=

n2 (n/4)2 (n/2)2

T(n/16) T(n/8) T(n/8) T(n/4)

=

n2 = (n/4)2 (n/2)2

n2 5/16 n2

(n/16) 2 (n/8) 2 (n/8) 2 (n/4) 2 25/256n2 …….. θ (1 ) θ (1 ) ……..θ (1 ) θ (1 )

上述递归树的叶节点是多少个？要注意的是，第 二层表示的意思是将问题规模为n的算法通过递归 将问题规模缩小为n/4+n/2=3n/4; 第三层最左分支表示的意思是将问题规模为n / 4 的算法通过递归将问题规模缩小为 n/16+n/8=3n/16; …… 因此叶节点的个数至少是小于n。

另外，递归树的另一个特点是左分支的分 解速度明显快于右分支，如第二层最左分 支为n / 4,最右分支为n /2;第三层最左分 支为n / 16,最右分支为n /4……因此左分 支递归树的深度要小于右分支的深度。

对各层求和，第一层的和是n2 ,第二层的 和是5/16n2 ((n/4)2 +(n/2)2 ),第三层的和是 52 /162 n2 ((n/16) 2 + (n/8) 2 +(n/8) 2 + (n/4) 2))….可以看出这是一个等比数列，对各层 累加， 即n2 + 5/16n2 +52 /162 n2 +… + 5k/16kn2 +… (1) (1) ≤(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2

等比数列性质： 1+1/2+1/4+1/8+…=2; 因为对二进制而言1+1/2=1.1 1+1/2+1/4=1.11 1+1/2+1/4+1/8+…=1.111…=2; 而(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2中 5/16< ½ 所以(1+ 5/16 +52 /162 +… + 5k/16k +… ) n2 ≤2 n2

故递归式T(n)= T(n/4)+ T(n/2)+n2的上界是 O (n2),下界是Ω (n2) (T(n)= T(n/4)+ T(n/2)+n2 ≥ n2)

递归树法又名递推法T(1)=1 T(n)=2T(n/2)+n2(n≥2) T(n)=2T(n/2)+ n 2 =2(2T(n/2 2)+(n/2) 2 )+ n2 =22T(n/22) +n2/2+ n2 =22(2T(n/23)+(n/22)2)+n2/2+ n2 =23(2T(n/23)+ n2/22+ n2/2+ n2 … =2kT(n/2k)+∑n2/2i (i从0到k-1)

本文来源：https://www.bwwdw.com/article/1234.html