Review of Divide and Conquer Lecture02动态规划 ■分:如何分:要考虑合 治:如何治:递归+临界条件下使用其它方 ■合:艺术!! ■递推公式。T(n)=T(n/b)+f(n) ■ Master定理:控制定理 Strassen矩阵乘法 矩阵乘法是线性代数中最常见的问题之一,它在数值计 ■矩阵相乘的分治算法( Strassen) Cj=∑Ak]BAⅡ ■其它的算法 要℃1每计题B的 元素所需的计算时间为0(n3) 20世纪60年代末期, Strassen采用了类似于在大整数乘 法中用过的分治技术,将计第2个阶矩阵乘积所需的计算时 其基本思想还是使用分治法。 清华太学未证想 将矩阵A,B和C中每一 分块成4个大小相等的子 如果n=2,则2个阶方阵的乘积可以直接计算出来 矩阵【假设n是2幂】,每个子矩阵都是(n/2)x(n2) 巨阵的阶大于时,为求2个 的方阵。由此可将方程 C=AB重写为 C1C12_4141TB1B 阶方阵的加法。2个(n2)×(n2)矩阵的加法显然 CnC2L41A2⊥B1B2 以在O(n2)时间内完成。因此,上述分治法的计算时间 耗费T 利用矩阵块乘可得 C12=A1B2+A2B2 O(1) C21=A2B1+A2B2 T(n)=1 清华大学 宋斌恒 1 Lecture 02 动态规划 清华大学 宋斌恒 清华大学 宋斌恒 2 Review of Divide and Conquer n 分：如何分：要考虑合 n 治：如何治：递归＋临界条件下使用其它方法 n 合：艺术！！！ n 递推公式。T(n)=aT(n/b)+f(n) n Master定理：控制定理 清华大学 宋斌恒 3 Strassen 矩阵乘法 n 矩阵相乘的分治算法（Strassen） n 其它的算法 清华大学 宋斌恒 4 矩阵乘法是线性代数中最常见的问题之一，它在数值计 算中有广泛的应用。设A和B是2个n×n矩阵，它们的乘积 AB同样是一个n×n矩阵。A和B的乘积矩阵C中元素C[i][j]定 义为： 若依此定义来计算A和B的乘积矩阵C，则每计算C的一 个元素C[i][j]，需要做n次乘法运算和n－1次加法运算。因 此，算出矩阵C中的n 2个元素所需的计算时间为O（n 3）。 20世纪60年代末期，Strassen采用了类似于在大整数乘 法中用过的分治技术，将计算2个n阶矩阵乘积所需的计算时 间改进到O（n log7）= O（n 2.81）, 其基本思想还是使用分治法。 å= = n k C i j A i k B k j 1 [ ][ ] [ ][ ] [ ][ ] 清华大学 宋斌恒 5 将矩阵A，B和C中每一矩阵都分块成4个大小相等的子 矩阵【假设n是2幂】，每个子矩阵都是（n/2）×（n/2） 的方阵。由此可将方程 C＝AB重写为： 利用矩阵块乘可得： ú û ù ê ë é ú û ù ê ë é =ú û ù ê ë é 21 22 11 12 21 22 11 12 21 22 11 12 B B B B A A A A C C C C 22 21 12 22 22 21 21 11 22 21 12 11 12 12 22 11 11 11 12 21 C A B A B C A B A B C A B A B C A B A B = + = + = + = + 清华大学 宋斌恒 6 如果n＝2，则2个2阶方阵的乘积可以直接计算出来， 共需8次乘法和4次加法。当子矩阵的阶大于2时，为求2个 子矩阵的积，可以继续将子矩阵分块，直到子矩阵的阶降 为2。由此产生分治降阶的递归算法。依此算法，计算2个 n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2 阶方阵的加法。2个（ n/2）×（ n/2）矩阵的加法显然可 以在O（n 2）时间内完成。因此，上述分治法的计算时间 耗费T（n）应满足： î í ì + > = = 8 ( / 2) ( ) 2 (1) 2 ( ) 2 T n O n n O n T n