数据结构-动态规划.ppt

复杂性分析 因此有 但需注意，在所有t(i)的调用中，只有第一次调用符合上面公式，其他均为Q(1) 因此易得，t(n)=Q(n) 迭代计算 void Vbits(int l[], int b[], int n, int s[], int kay[]) {// Compute s[i] and kay[i] for all i. int L = 256, header = 11; s[0] = 0; // compute s[i] using Eq. 15.3 for (int i = 1; i = n; i++) { // compute min term for k = 1 int lsum = l[i], bmax = b[i]; s[i] = s[i - 1] + lsum * bmax; kay[i] = 1; 迭代计算（续） // compute for remaining k and update for (int k = 2; k = i lsum+l[i-k+1] = L; k++) { lsum += l[i-k+1]; if (bmax b[i-k+1]) bmax = b[i-k+1]; if (s[i] s[i-k] + lsum * bmax) { s[i] = s[i-k] + lsum * bmax; kay[i] = k;} } s[i] += header; } } 15.2.3 矩阵乘法链 m×n矩阵与n×p矩阵相乘，Q(mnp) (A×B)×C与A×(B×C)复杂性完全不同 例：A：100×1，B：1×100，C：100×1 A×B?D，时间10000，D：100×100D×C，时间1000000，总时间1010000 B×C?D，时间10000，D：1×1A×D，时间100，总时间10100 空间复杂性也是后者占优 例：图像处理 两个三维图像匹配问题：一个图像经旋转、平移、缩放多少次才能逼近另一图像？ 算法：100次迭代，每次计算12×1向量 A、B、C为12×1，3×3，3×1的矩阵，(x,y,z)为图像中向量的坐标，t表示矩阵相乘时间 例：图像处理 图像有256*256*256个向量?总时间100*2563t≈1.7*109t 由左至右相乘t=12*3*3+12*3*1=144自右至左相乘t=3*3*1+12*3*1=45 性能差异是巨大的 动态规划解法 矩阵M1, ..., Mq，Mi是ri×ri+1矩阵 q↑，乘法计算方法指数↑ 动态规划算法，复杂性下降为Q(q3) Mij：Mi×...×Mj cij：计算Mij的最优时间 kay(i, j)：Mij最优计算方法最后一步的计算位置，即Mij=Mik×Mkj 递推公式 例 q=5，r=(10,5,1,10,2,10) c(1,5)=min{c(1,1)+c(2,5)+500, c(1,2)+c(3,5)+100, c(1,3)+c(4,5)+1000, c(1,4)+c(5,5)+200} c(1,1)=c(5,5)=0，c(1,2)=50，c(4,5)=200 c(2,5)=min{c(2,2)+c(3,5)+50, c(2,3)+c(4,5)+500, c(2,4)+c(5,5)+100} c(2,2)=c(5,5)=0；c(2,3)=50；c(4,5)=200 c(3,5)=min{c(3,3)+c(4,5)+100, c(3,4)+c(5,5)+20} = min{0+200+100, 20+0+20}=40，kay(3,5)=4 c(2,4)=min{c(2,2)+c(3,4)+10, c(2,3)+c(4,4)+100} = min{0+20+10, 50+10+20}=30，kay(2,4)=2 ?c(2,5)=min{0+40+50, 50+200+500, 30+0+100}=90，kay(2,5)=2 例（续） 计算c(1,5)还需算出c(3,5)、c(1,3)和c(1,4)。类似过程，可得它们的值分别为40、150和90，相应的kay值分别为4、2和2?c(1,5)=min{0+90+500, 50+40+100, 150+200+1000, 90+0+200}=190且kay(1,5)=2 ?最后一步计算M12×M35由kay(1,2)=1知M12=M11×M22由kay(3,5)=4知M35=