T(n)
=n
n/2
n/2
n/2
n/2
T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n/4)T(n/4)T(n/4)
2020/6/14
4
Fibonacci sequence(序列)
蛮力法: 列举A所以的2n个子序列, 对于每一子序 列在(m)时间内来确定它是否也是B的子序列.
很明显, 此算法的时间复杂的为(m*2n).
2020/6/14
10
ห้องสมุดไป่ตู้推公式
为了使用动态规划技术, 首先推导一个求最长公 共子序列长度的递推公式. 令A=a1a2...an和B=b1b2...bm 令L[i, j]表示a1a2...ai和b1b2...bj的最长公共子 序列的长度(i, j可能是0, 此时a1a2...ai和 b1b2...bj中至少一个为空). 可得如下结论：
对于给定的一对索引i和j, 1i<jn, Mi,j可用如 下方法计算:
设k是i+1和j之间的一个索引, 计算两个矩阵 Mi,k-1=MiMi+1…Mk-1和Mk,j=MkMk+1…Mj, 那么 Mi,j=Mi,k-1Mk,j
显然, 用这种方法计算Mi,j的总耗费, 是计算Mi,k-1的 耗费加上计算Mk,j的耗费, 再加上Mi,k-1乘以Mk,j的耗 费(rirkrj+1), 因此得到了如下的公式:
7y 0 1 2 2 3 3 3 4 4 5 5 5 5
8z 0 1 2 3 3 3 4 4 4 5 5 5 6
9x 0 1 2 3 3 3 4 5 5 5 6 6 6
10y 0 1 2 3 4 4 4 5 5 6 6 6 6
2020/6/14
图7.1 最长公共子序列问题的一个例子
17
Algorithm 7.1pro LCS 1. for i0 to n 2. L[i, 0]0 3. end for 4. for j0 to m 5. L[0, j]0 6. end for 7. for i1 to n 8. for j1 to m 9. if ai=bj then L[i, j]L[i-1, j-1]+1, b[i, j]”\”
2020/6/14
13
Algorithm 7.1 LCS Input: Two strings A and B of length n and m, respectively, over an alphabet
Output: The length of the longest common subsequence of A and B
((AB)(CD))
乘法次数: 36000
(((AB)C)D)
乘法次数: 87500
((A(BC))D)
乘法次数: 34500
2020/6/14
24
Matrix chain multiplication矩阵链相乘
一般情况下, n个矩阵链M1M2...Mn相乘的耗费, 取 决于n-1个乘法执行的顺序(结合方式).
2020/6/14
6
Fibonacci sequence分析
f(n)= f(n-1)+ f(n-2)
=2f(n-2)+ f(n-3)
=3f(n-3)+2f(n-4)
=5f(n-4)+3f(n-5)
T(n) 1T(n1)T(n2)
if n1,2 if n3
f (n)(n),where1 5
2
2020/6/14
15
定理7.1 最长公共子序列问题的 最优解能够在(nm)时间和 (min{m, n}) 空间内得到.
？
2020/6/14
16
A=“xyxxzxyzxy” B=“zxzyyzxxyxxz”
0 1z 2x 3z 4y 5y 6z 7x 8x 9y 10x 11x 12z
0 00 0 0 0 0 0 0 0 0 0 0 0
1. for i0 to n 2. L[i, 0]0 3. end for 4. for j0 to m 5. L[0, j]0 6. end for
2020/6/14
14
7. for i1 to n 8. for j1 to m 9. if ai=bj then L[i, j]L[i-1, j-1]+1 10. else L[i, j]max{L[i, j-1], L[i-1, j]} 11. end if 12. end for 13. end for 14. return L[n, m]
如果采用自顶向下的方式不能得到有效的算法, 导致巨大的重复递归调用.
2020/6/14
27
Illustration of matrix chain multiplication矩阵链乘图示
2020/6/14
28
Algorithm 7.2 MATCHAIN
Input: An array r[1..n+1] of positive integers corresponding to the dimensions of a chain of n matrices, where r[1..n] are the number of rows in the n matrices and r[n+1] is the number of columns in Mn
2020/6/14
20
2020/6/14
21
算法的改进
在算法lcs和print-LCS中, 可进一步将数组b省 去. 事实上, 数组元素L[i][j]的值仅由L[i-1][j-1], L[i-1][j]和L[i][j-1]这3个数组元素的值所确定. 对于给定的数组元素L[i][j], 可以不借助于数组 b而仅借助于L本身确定L[i][j]的值是由L[i1][j-1], L[i-1][j]和L[i][j-1]中哪一个值所确定的.
和前面的方法相比, 可以很大程度降低时间复杂 度.
2020/6/14
9
The longest common subsequence problem最长公共子序列问题
在字母表上, 分别给出两个长度为n和m的字符 串A和B, 确定在A和B中最长公共子序列的长度.
这符里串A, 其=a中1a每2...个ani的j在子1到序n列之的间一, 个并形且式1为i1<aii21<a.i.2..<..iakik的n 字
ma L[ix ,j {1]L ,[i1,j]}ifi0,j0anaid bj
2020/6/14
12
现在可以直接用动态规划技术来求解最长 公共子序列问题。对每一对i和j的值，0 i n，0 j m，我们用一个(n+1)×(m+1) 表来计算L[i, j]的值，只需要用上面的公式 逐行地填表L[0…n, 0…m]。算法如下：
2020/6/14
23
Matrix chain multiplication矩阵链相乘
设有4个矩阵A, B, C, D, 它们的维数分别是 A:5010 B:1040 C:4030 D:305, 共有5种加括号 的方式：
(A((BC)D))
乘法次数: 16000
(A(B(CD)))
乘法次数: 10500
2020/6/14
7
二项式系数的计算
1
n k
n k
1 1
n k
1
n k
n! k!(n
k )!
由 Stirling 等式，有
if k 0 or k n if 0 k n
n k
n! (( n / 2 )! ) 2
2nn n / en n(n / 2)n / en
2n n
有效计算上式的方法是按行构造帕斯卡三角形
2020/6/14
26
C [ i,j] m i k j{ C [ i,k n 1 ] C [k ,j] r ir k r j 1 }
Particularly,
C [ 1 ,n ] 1 m k n { C [ 1 , ik n 1 ] C [ k ,n ] r 1 r k r n 1 }
Fibonacci序列定义如下：
1. procedure f(n)
2. if n=1 or n=2 then return 1
3. else return f(n-1)+f(n-2)
这种递归形式有简洁、容易书写和容易查错等 优点, 最主要是它的抽象性.
但是它远不是有效的算法.
算法复杂性: (n) Why???
蛮力算法: 计算出每一种可能顺序的数量乘法次 数.
时间复杂度是：
算法复杂度分析： 对于n个矩阵的连乘积, 设其不同的计算次序为P(n). 由于每种加括号方式都可以分解为两个子矩阵的加括号问题： (A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：
P (n ) n 1P (k)1 P (nk) k 1
1x 0 0 1 1 1 1 1 1 1 1 1 1 1
2y 0 0 1 1 2 2 2 2 2 2 2 2 2
3x 0 0 1 1 2 2 2 3 3 3 3 3 3
4x 0 0 1 1 2 2 2 3 4 4 4 4 4
5z 0 1 1 2 2 2 3 3 4 4 4 4 5
6x 0 1 2 2 2 2 3 4 4 4 5 5 5
19. return L[n, m] and b[n, m]
2020/6/14
19
print-LCS(b, A, i, j) 1. if i=0 or j=0 then return 2. if b[i, j]= ”\” then 3. print-LCS(b, A, i-1, j-1) 4. print ai 5. else 6. if b[i, j]= ”” then print-LCS(b, A, i-1, j) 7. else print-LCS(b, A, i, j-1) 8. end if