建立递归关系 ■令m[],1,jn,为计算A[,j的最少数乘 次数,则原问题为m[[n] 当i=j时,A[i,j为单一矩阵,m[i[=0; 当<j时,利用最优子结构性质有: m[][]=min(m1]k]+mk+1]0]+ pi-lPkPj J 其中矩阵A,1≤n,的维数为p1×p ■根据此递归式就可以直接用递归程序来实现 算法设计与分析 6
算法设计与分析 6 建立递归关系 ◼ 令m[i][j] , 1≤i, j≤n，为计算A[i, j] 的最少数乘 次数，则原问题为m[1][n]。 ◼ 当i = j时，A[i, j]为单一矩阵， m[i][j] = 0； ◼ 当i＜j时，利用最优子结构性质有： m[i][j] = min{m[i][k] + m[k+1][j] + pi–1pkpj} i≤k＜j 其中矩阵Ai ，1≤i≤n，的维数为pi–1×pi。 ◼ 根据此递归式就可以直接用递归程序来实现
直接递归的时间复杂性 ■根据前面的递归式不难得出的时间复杂性为 T()>1+x(T(k)+T(nk)+1) 1+(n-1)+x(T(k)+T(n-k) =n+T(k)+∑T(n-k) n+2∑T(k) ■可用数学归纳法证明T(n)≥2n1=92(2) ■直接递归算法的时间复杂性随n的指数增长。 算法设计与分析
算法设计与分析 7 直接递归的时间复杂性 ◼ 根据前面的递归式不难得出的时间复杂性为 n–1 1 + ∑(T(k) + T(n–k) + 1) k=1 T(n) ≥ n–1 = 1 + (n – 1) +∑(T(k) + T(n–k)) k=1 n–1 n–1 = n +∑T(k) + ∑T(n–k) k=1 k=1 ◼ 可用数学归纳法证明T(n)≥2n–1 = Ω(2n )。 ◼ 直接递归算法的时间复杂性随n的指数增长。 n–1 = n + 2∑T(k) k=1
直接递归中有大量重复计算 ■直接递归中有大量重复计算,如A[1:4]计算中 1:4 图中红框标出的 都是重复计算 1:2 3:4 2:4 1:112:23:314:4 4:4 2:23:42:3‖4:4 1:12:31:23:3 3:3‖14:42:2‖3:3 2233[1:122 算法设计与分析
算法设计与分析 8 直接递归中有大量重复计算 ◼ 直接递归中有大量重复计算，如A[1: 4]计算中： 1: 4 1: 1 2: 4 1: 2 3: 4 1: 3 4: 4 2: 2 3: 4 2: 3 4: 4 1:1 2: 2 3: 3 4: 4 1: 1 2: 3 1: 2 3: 3 3: 3 4: 4 2: 2 3: 3 2: 2 3: 3 1: 1 2: 2 图中红框标出的 都是重复计算
消除重复的计算 ■要消除重复计算,可在在计算过程中保存已解 决的子问题的答案。这样,每个子问题只计算 次,而在后面需要时只要简单查一下,从而 避免重复计算 计算方式可依据递归式自底向上地进行。 注意到在此问题中,不同的有序对(j)就对应 不同的子问题,因此不同的子问题个数个数最 多只有C2+n=0(n2)个。 这样便可以得到多项式时间的算法 算法设计与分析 9
算法设计与分析 9 消除重复的计算 ◼ 要消除重复计算，可在在计算过程中保存已解 决的子问题的答案。这样，每个子问题只计算 一次，而在后面需要时只要简单查一下，从而 避免重复计算。 ◼ 计算方式可依据递归式自底向上地进行。 ◼ 注意到在此问题中，不同的有序对 (i, j)就对应 不同的子问题，因此不同的子问题个数个数最 多只有Cn 2+ n = (n 2 )个。 ◼ 这样便可以得到多项式时间的算法
自底向上的计算 ■例如对于A1A2A3A4,依据递归式以自底向上的 方式计算出各个子问题,其过程如下 m24例如:m[3]= m[1+m[2][3]+popp m(l31 m(2114 min (m[1 J(2]+m[3J(3]+PoP2P3 m2】m2]|m34m订计+1]=ppp mum22m33m44m[=0 算法设计与分析 10
算法设计与分析 10 自底向上的计算 ◼ 例如对于A1A2A3A4，依据递归式以自底向上的 方式计算出各个子问题，其过程如下： m[1][1] m[2][2] m[3][3] m[4][4] m[1][2] m[2][3] m[3][4] m[1][3] m[2][4] m[2][4] 其中 m[i][i] = 0 m[i][i+1] = pi–1pipi+1 m[i][j] = mini≤k＜j {m[i][k]+m[k+1][j]+pi–1pkpj} 例如： m[1][3] = min m[1][1]+m[2][3]+p0p1p3 m[1][2]+m[3][3]+p0p2p3