2c n−1 右边 = ∑ i log i + n + 1 n i =1 2c n 2 n2 = [ log n − + O( n log n)] + n + 1 n 2 4 ln 2 c )n + O (log n) = cn log n + (1 − 2 ln 2
n
1 x2 x x2 ∫ x log xdx = ∫ ln 2 ln xdx = ln 2 [ 2 ln x − 4 ] 2 2
归并排序 n− W(n) = 2W(n/2) + n−1 a = 2, b = 2, d(n) = O(n), W(n)= O(nlogn)
位乘问题：X,Y 为 n 位二进制数，n=2 , 求 XY 位乘问题： 位二进制数， 2 一般方法 W(n)= O(n ) 分治法： 分治法：令 X = A2 + B, Y = C2 + D, 则 n n/2 XY = AC 2 + (AD+BC)2 + BD W(n)= 4 W(n/2) + cn W(1)= 1 log4 2 a = 4，b = 2, W(n)= O(n )= O(n ) 变换： (A-B)(D变换：AD + BC = (A-B)(D-C) + AC + BD W(n) = 3 W(n/2) + cn W(1)= 1 a = 3，b = 2, W(n)= O(n
二分搜索 W(n) = W(n/2) + 1 a = 1, b = 2, d(n) = c W(n) = O(logn)
(1) d(n)=cn
a i T ( n) = a + ∑ a i = a + cn ∑ ( ) b i =1 i =1 b
k i k k −1
cn
k −1
log a (a / b) k − 1 a<b = O( n) n b + cn a/b−1 a=b = n + cnk = O ( n log n) k (a / b ) k − 1 a k − bk = ak + c = O ( n log b a ) a > b a + cn a/b−1 a/b−1
解：先化简，再迭代 先化简， (nDn = (n-1)(Dn-1 + Dn-2)
Dn − nDn−1 = −[ Dn−1 − ( n − 1) Dn− 2 ] = ... = ( −1) n− 2 [ D2 − 2 D1 ] = ( −1) n− 2 Dn = nDn−1 + ( −1) n , D1 = 0 Dn = n( n − 1) Dn− 2 + n( −1) n−1 + ( −1) n = n( n − 1)( n − 2) Dn− 3 + n( n − 1)( −1) n− 2 + n( −1) n−1 + ( −1) n = ... = n( n − 1) ... 2 D1 + n( n − 1) ... 3( −1) 2 + n( n − 1) ... 4( −1) 3 + ... + n( −1) n−1 + ( −1) n 1 1 1 = n![1 − + − ... + ( −1) n ] 1! 2! n!
1 1 1 n+1 1 + + ... + ≤ ∫ dx n+1 n 3 2 x = ln x
n+1 2
= ln( n + 1) − ln 2 = O (log n)
四、尝试法 例7 (1)
2 n −1 T ( n) = ∑ T ( i ) + n + 1 n i =1
左边=O(1) =O(1)， T(n)=C, 左边=O(1)，
k k k k k
*
n = 2
k
k
k
非常系数线性，特别是减半递推） 二．叠代归纳法 （非常系数线性，特别是减半递推） 例 3 计数 a1,a2,…,an 相乘的方法数 ,a (4nh(n (nh(n) = (4n-6) h(n-1) h(1) = 1
h( n) = ( 4n − 6) h( n − 1) = (4n − 6)(4n − 10) h( n − 2) = ... = (4n − 6)(4n − 10) ... 6 ⋅ 2 ⋅ h(1) = 2 n −1 [( 2n − 3)( 2n − 5) ... 3 ⋅ 1] ( 2n − 2)! ( 2n − 2)! = 2 n −1 = ( 2n − 2)( 2n − 4) ... 4 ⋅ 2 ( n − 1)!
i =1 n −1
( n − 1)T ( n − 1) = 2 ∑ T ( i ) + ( n − 1) 2 + ( n − 1)
i =1
n− 2
nT ( n) − ( n − 1)T ( n − 1) = 2T ( n − 1) + 2n nT ( n) = ( n + 1)T ( n − 1) + 2n T ( n) T ( n − 1) 2 2 2 2 T (1) = + = + + ... + + n+1 n n+1 n+1 n 3 2 1 1 1 = 2 + + ... + = O (log n) 3 n + 1 n T ( n) = O( n log n)
* 2 * 2 a n = P1n + P2 n , 解得 a n = n - n 2 C⋅ n a n = C ⋅1 + n – n n 2 2 2 a n= 2 + n – n = n - n + 2 2 2 * 2 * 2
（代入初值） 代入初值）
例 9 分治策略与递归算法 为输入规模， 为子问题输入规模， n 为输入规模，n/b 为子问题输入规模， 为子问题个数，d(n)为分解及综合的代价 a 为子问题个数，d(n)为分解及综合的代价
k k −1 i =0
a i d (n / bi ) ∑
a =a
k
log b n
=n
log b a
T ( n) = a k +
(1) d(n)=c
k −1 i =0
a i d ( n / b i ), a k = n log b a ∑
k ak − 1 a + c = O (a k ) = O ( n log b a ) a ≠ 1 T ( n) = a −1 a k + kc = O ( kc ) = O (log n) a =1
T ( n) = aT ( n / b ) + d ( n), n = b k T (1) = 1 T ( n) = a 2T ( n / b 2 ) + ad ( n / b ) + d ( n) = ... = a k T ( n / b k ) + a k −1d ( n / b k −1 ) + a k − 2 ( n / b k − 2 ) + ... + ad ( n / b ) + d ( n) =a +
Partition(A,1,13)的实例： 的实例： 的实例
27 99 i 25 0 8 13 64 86 16 7 10 88 25 j 99 90
27
0
8
13
64 i 10
86
16
7
10 j 64
88
90
27
25
0
8
13
86 i 7
16
7 j 86 i 86
88
99
90
27
25
0
8
13
10
16 j 27
(3)
左边=cn T(n)=cn2, 左边=cn2
2 n −1 2 右边 = ∑ ci + n + 1 n i =1 2 cn 3 2c 2 n + O ( n) = [ + O ( n 2 )] + n + 1 = n 3 3
(4)
T(n)=cnlogn , 左边=cnlogn 左边=cnlogn
第二节 递推方程的其他解法 主要内容 换元法 迭代归纳法--递归树 迭代归纳法--递归树 -差消法 尝试法 应用实例
一、换元法 思想：通过换元转化成常系数线性递推方程 思想：通过换元转化成常系数线性递推方程 例1
2 2 a n = 2a n − 1 + 1 a0 = 2
2 令 bn = a n , 代入得
用归纳法验证. 用归纳法验证.
例4
错位排列问题 {1,2,…,n}的排列 i,i=1,2,…,n， {1,2,…,n}的排列 a1a2…an,ai≠i,i=1,2,…,n，
错位排列定义： 错位排列定义： 个元素的错位排列数记作 n 个元素的错位排列数记作 Dn 2,3,… 分类： 将错位排列按首元素 2,3,…,n 分类：有 n-1 类， 第一位为 2 的类： 的类： 第二位为 1： 递推方程： 递推方程： (nDn = (n-1)(Dn-1+Dn-2) D1 = 0, D2 = 1 方法数为 Dn-2 第二位不是 1：方法数为 Dn-1
64
88
99
90
16
25
0
8
13
10
7
64
88
99
90
时间复杂度分析 时间复杂度分析 最坏情况
W ( n ) = W ( n − 1) + n − 1 W (1) = 0 1 W ( n ) = n( n − 1) = Θ( n 2 ) 2