2017/3/13 计算机算法设计与分析 16
分治策略的算法分析工具：递推方程 两类递推方程
如：汉诺塔
f ( n) a i f ( n i ) g( n)
i 1
k
n f ( n) af ( ) d ( n) b
如：快速排序
17
递推方程的解
方程
T (n) aT(n / b) d (n)
O ( n log b a ) a 1 T ( n) O (log n) a 1
ab O( n) T ( n) O( n logn) a b O( n log b a ) a b
d(n)为常数
d(n) = cn
影响复杂性的主要因素：子问题个数，合 并开销函数。
如何计算算法时间复杂度
计算算法时间复杂度过程： （1）确定基本操作 （2）构造基于基本操作的函数解析式 （3）求解函数解析式
如果构建的是递推关系式，那么常 用的求解方法有： （1）前向替换法 可以从初始条件给出的序列初始项 开始，使用递推方程生成序列的前面 若干项，寄希望于从中找出一个能够 用闭合公式表示的模式。如果找到了 这样的公式，我们可以用两种方法对 它进行验证：第一，将它直接代入递 归方程和初始条件中。第二，用数学 归纳法来证明。
T (1) 1 T (n) m T(n / m) O(n)
算法的复杂度有两部分决定：递归和合并， 递归的复杂度是：n， 合并的复杂度是 nlogn。
减治法的基本思想
• 将规模为n的问题递减为规模为n-1或n/2的子问题
,反复递减后对子问题分别求解,再建立子问题的解 与原问题的解的关系。 • 减治法有两个变形: 减因子(如1/2):每次迭代规模减半n→ n/2 减可变规模:每次迭代减小的规模不同
X(n)=x(0)+1+2+3+4+5…+n=0+1+2+3=4 = n(n+1)/2
（3）换名
f (n) f (n / k ) b
上面形式的在递推关系式，一个规模为n的问题， 每一次递归调用后，都简化为n/k规模的问题，为了 方便求解，我们通常设定：n=km， 则，上面的求解过程可简化为： f(n)= f(km-1)+b = f(km-2)+2b =… = f(k0)+mb = f(1) + blog n
第二种递归调用，每次规模是原来的1/2：
1 T (n) T (n / 2) (n 1)
设 n = 2k： T(n) = T(n/2) + (n-1)
n 1 n 1
因为每一次规模都减到原来的1/2，所以用换名的方法
= T(2k-1) + (2k-1)
=[T(2k-2) + (2k-1-1)]+ (2k-1) =… =[T(2k-k) + (21-1)] + … +(2k-1-1) +(2k-1) =T(1)+[(2k+1-2)-k]
=2n-logn-1
算法时间复杂度：O(n) 分析：
1 T (n) T (n / 2) (n 1) n 1 n 1
算法的复杂度有两部分决定：递归和合并， 递归的复杂度是：logn， 合并的复杂度是 n。
第三种递推关系式：
T (2) 1 T (n) 2T (n / 2) O(n)
T(n)=2T(n/2) +n 设n= 2k =2T(2k-1)+2k =2[2T(2k-2)+2k-1]+2k =22T(2k-2)+2*2k =… =2k-1T(2k-(k-1)) + (k-1)*2k =n/2 + (logn-1) *n
不失一般性，设规模为n的问题，每一次有 分解为m个子问题，设n =mk，则：
T (1) 1 T (n) mT(n / m) O(n)
T(n)=mT(n/m) +n =mT(mk-1)+mk =m[mT(mk-2)+mk-1]+mk =m2T(mk-2)+2*mk =… =mkT(2k-k) + k*mk =n + logn *n
算法时间复杂度：O(nlogn) 分析：
第一种递归关系式：
1 C ( n) C ( n / 2) 1
n 1 n 1
因为规模每一次递归调用后，缩减为原来的1/2，所以采用换 名方法求解，设 n = 2k：
C(n) = C(2k)= C(2k-1)+1 = C(2k-2) + 2 =… =C(2k-k)+k =C(1) + k = logn+1
递归复杂性的一般形式
• 一般的，递归复杂性可描述为递归方程： f(n) = 1 n=1 af(n ~ b) + D(n示递减方式， b是递减步长， D(n)是合成子问题的开销。 • 通常，递归元的递减方式~有两种： 递推法 1、减法，即n – b，的形式。 分治法 2、除法，即n / b，的形式；
例如，考虑如下递推式： X(n) = 2X(n-1) +1 n>1 X(1) = 1 x(1)=1 x(2)=2x(1)+1 = 2*1+1=3 x(3)=2x(2)+1=2*3+1=7 x(4)=2x(3)+1=2*7+1=15
X(n)=2^n-1
n>0
（2）反向替换法
例如：X(n)=x(n-1)+n 使用所讨论的递推关系，将x(n-1)表 示为x(n-2)得函数，然后把这个结果 代入原始方程，来把x(n)表示为x(n-2) 的函数。重复这一过程。