※ 引述《sky810675 (KKMAN)》之铭言： : 不好意思!想请问说以下有4个矩阵!A3*5,B5*2,C2*4,D4*6 : 其中: : A(BC)=(5*2*4)+(3*5*4)=40+60=100 : (AB)C=(3*5*2)+(3*2*4)=30+24=54 : 想知道为什麽A(BC)与(AB)C会得到这样的分解运算呢? : 不好意思><因为已经想很久一直找不出规律性!谢谢 : http://140.113.149.29/blog/?p=8666 : 虽然有连结!但前面那个还是不太懂 其实你可以看看在求BC的过程中,要用到几次乘法: B: 5 X 2 C: 2 X 4 你如果下去试,应该可以知道得到 (BC) (矩阵BC的第j行) , 1<=j<=4 j 需要做 5X2 次乘法 Ex: [ 1 1] [ 1 1] [1 1 1 1] B = [ 1 1] , C = [1 1 1 1] [ 1 1] [ 1 1] [1*1+1*1] =>2次 => (BC) = [1*1+1*1] =>2次 1 [1*1+1*1] =>2次 => 共10次 [1*1+1*1] =>2次 [1*1+1*1] =>2次 得到BC,要求出 (BC) (BC) (BC) (BC) ,每个都要做10次乘法 1, 2, 3, 4 则要10*4=40次乘法,其实就是 5*2*4,并得到一个 大小为 5 X 4的矩阵 如果你理解这个特性的话, 你可以想见 A(BC) 需要 3 X 5 X 4 = 60次乘法 故以上对法的运算量共 40 + 60 = 100 --------------------------------------------------------------------- 另一方面,如果是 先算AB,再乘以C呢? A: 3 X 5 B: 5 X 2 5 (AB) = Σ a b => 每求一个元素要做5次 ij k=1 ik kj 你可以想见 AB的大小是 3 X 2 = 6 所以需要 5 X 6 = 30 = 3 X 5 X 2 次乘法 AB : 3 X 2 C : 2 X 4 如果你现在有一点勇气,应该可以马上回答: (AB)C要做 3 X 2 X 4 = 24乘法 Rule: 左矩阵的Row size X 两矩阵共同的 size X 右矩阵的 Column Size (因为矩阵可乘的条件是:左矩阵的 Column Size = 右矩阵的 Row Size, 又必须在求每一个元素的过程中,走过"两矩阵共同的 size"次,才能做完, 所以会多中间那一项) -------------------------------------------------------------------- Note: 这其实是出自演算法的章节: dynamic programming(动态规划), 它的观点是: 我们做矩阵连乘时,如果总是从左边算到右边,不见得会比从中间某 段算,来的有效率(计算次数未必较少),所以我们希望找出一个演算法,使得 作矩阵连乘的运算次数能够最少(这里是着重在做乘法的部分) 那我们发现到矩阵乘法具有结合律,这表示我们不一定要按照顺序算过来 要达到这一点必须要: (1) 找出衡量矩阵运算次数的衡量标准(像这里是对乘法), 同时要达到最小的规则是什麽 你问的问题,就是在做这件事 (2) 既然我们找到法则了, 那我们要在运算过程中记住这些资讯, 并且不断的更新(如果找到更好得方法的话),最後应该可以得到 最佳解 => dynamic progamming的精随 你可以参考一些演算法课本,像: (1) Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein 一般学校都会用这一本,内容很多,但对初学者来说,不算很容易,不过里面都会先讲 演算法的观点,再去做一些演算法的分析和证明,他的习题必须要你对里面的内容很 了解,才做得出来 (2) Foundations of Algorithms, Fourth Edition by Richard Neapolitan and Kumarss Naimipour 有在书局看过一次,觉得也不差 (3) Introduction to the Design and Analysis of Algorithms (2nd Edition) by Anany Levitin (有中文版) 这一本好像是最好读的,不过好像不着重分析,但会告诉你演算法的直觉, 另外,会有习题提示,但就不知有没有帮助了 此外,要了解演算法的思维,必须要有一定的程式经验,否则你可能会觉得: 虽然 里面的运算操作很简单,为什麽还要提出这些演算法? 或者你可能认为,直接作很简单. 卫门麽要搞得那麽复杂? 以上是我个人的意见,如果有觉得不对,不认同或是要补充的,欢迎尽量提出来 (不过那个网站很多都写得比我好~~) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 111.243.175.119 ※ 编辑: yueayase 来自: 111.243.175.119 (03/08 00:42) ※ 编辑: yueayase 来自: 111.243.175.119 (03/08 00:49)