施特拉森演算法, 此條目或其章節极大或完全地依赖于某个单一的来源, 2014年9月3日, 请协助補充多方面可靠来源以改善这篇条目, 致使用者, 请搜索一下条目的标题, 来源搜索, 网页, 新闻, 书籍, 学术, 图像, 以检查网络上是否存在该主题的更多可靠来源, 判定指引, 英語, strassen, algorithm, 是一個計算矩陣乘法的演算法, 時間複雜度為o, displaystyle, 目录, 簡介, 算法, 定義, 計算, 評論, 相關連結, 参考来源簡介, 编辑, nbsp, 矩陣乘法演算法的演進,. 此條目或其章節极大或完全地依赖于某个单一的来源 2014年9月3日 请协助補充多方面可靠来源以改善这篇条目 致使用者 请搜索一下条目的标题 来源搜索 施特拉森演算法 网页 新闻 书籍 学术 图像 以检查网络上是否存在该主题的更多可靠来源 判定指引 施特拉森演算法 英語 Strassen algorithm 是一個計算矩陣乘法的演算法 時間複雜度為O n log 2 7 O n 2 807 displaystyle O n log 2 7 O n 2 807 目录 1 簡介 2 算法 2 1 定義 2 2 計算 3 評論 4 相關連結 5 参考来源簡介 编辑 nbsp 矩陣乘法演算法的演進 施特拉森演算法在1969年由沃爾克 施特拉森所提出 是第一個時間複雜度低於O n 3 displaystyle O n 3 nbsp 的矩陣乘法演算法 由於演算法簡單理解 且為第一個被提出來的特性 常被演算法教材拿來當作主定理 英語 Master theorem 計算時間複雜度的例子 另外 因為施特拉森演算法證明了矩陣乘法存在時間複雜度低於O n 3 displaystyle O n 3 nbsp 的演算法 使得更多學者投入研究 尋找更快的演算法 算法 编辑定義 编辑 設A displaystyle A nbsp B displaystyle B nbsp 為域F displaystyle F nbsp 上的方矩陣 求兩者的積C displaystyle C nbsp 一般矩陣可以填0的方法計算令它成為2 n 2 n displaystyle 2 n times 2 n nbsp 矩陣 C A B A B C F 2 n 2 n displaystyle mathbf C mathbf A mathbf B qquad mathbf A mathbf B mathbf C in F 2 n times 2 n nbsp 計算 编辑 將A B C分成相等大小的方塊矩陣 A A 1 1 A 1 2 A 2 1 A 2 2 B B 1 1 B 1 2 B 2 1 B 2 2 C C 1 1 C 1 2 C 2 1 C 2 2 displaystyle mathbf A begin bmatrix mathbf A 1 1 amp mathbf A 1 2 mathbf A 2 1 amp mathbf A 2 2 end bmatrix mbox mathbf B begin bmatrix mathbf B 1 1 amp mathbf B 1 2 mathbf B 2 1 amp mathbf B 2 2 end bmatrix mbox mathbf C begin bmatrix mathbf C 1 1 amp mathbf C 1 2 mathbf C 2 1 amp mathbf C 2 2 end bmatrix nbsp 即 A i j B i j C i j F 2 n 1 2 n 1 displaystyle mathbf A i j mathbf B i j mathbf C i j in F 2 n 1 times 2 n 1 nbsp 於是 C 1 1 A 1 1 B 1 1 A 1 2 B 2 1 displaystyle mathbf C 1 1 mathbf A 1 1 mathbf B 1 1 mathbf A 1 2 mathbf B 2 1 nbsp C 1 2 A 1 1 B 1 2 A 1 2 B 2 2 displaystyle mathbf C 1 2 mathbf A 1 1 mathbf B 1 2 mathbf A 1 2 mathbf B 2 2 nbsp C 2 1 A 2 1 B 1 1 A 2 2 B 2 1 displaystyle mathbf C 2 1 mathbf A 2 1 mathbf B 1 1 mathbf A 2 2 mathbf B 2 1 nbsp C 2 2 A 2 1 B 1 2 A 2 2 B 2 2 displaystyle mathbf C 2 2 mathbf A 2 1 mathbf B 1 2 mathbf A 2 2 mathbf B 2 2 nbsp 引入新矩陣 M 1 A 1 1 A 2 2 B 1 1 B 2 2 displaystyle mathbf M 1 mathbf A 1 1 mathbf A 2 2 mathbf B 1 1 mathbf B 2 2 nbsp M 2 A 2 1 A 2 2 B 1 1 displaystyle mathbf M 2 mathbf A 2 1 mathbf A 2 2 mathbf B 1 1 nbsp M 3 A 1 1 B 1 2 B 2 2 displaystyle mathbf M 3 mathbf A 1 1 mathbf B 1 2 mathbf B 2 2 nbsp M 4 A 2 2 B 2 1 B 1 1 displaystyle mathbf M 4 mathbf A 2 2 mathbf B 2 1 mathbf B 1 1 nbsp M 5 A 1 1 A 1 2 B 2 2 displaystyle mathbf M 5 mathbf A 1 1 mathbf A 1 2 mathbf B 2 2 nbsp M 6 A 2 1 A 1 1 B 1 1 B 1 2 displaystyle mathbf M 6 mathbf A 2 1 mathbf A 1 1 mathbf B 1 1 mathbf B 1 2 nbsp M 7 A 1 2 A 2 2 B 2 1 B 2 2 displaystyle mathbf M 7 mathbf A 1 2 mathbf A 2 2 mathbf B 2 1 mathbf B 2 2 nbsp 可得 C 1 1 M 1 M 4 M 5 M 7 displaystyle mathbf C 1 1 mathbf M 1 mathbf M 4 mathbf M 5 mathbf M 7 nbsp C 1 2 M 3 M 5 displaystyle mathbf C 1 2 mathbf M 3 mathbf M 5 nbsp C 2 1 M 2 M 4 displaystyle mathbf C 2 1 mathbf M 2 mathbf M 4 nbsp C 2 2 M 1 M 2 M 3 M 6 displaystyle mathbf C 2 2 mathbf M 1 mathbf M 2 mathbf M 3 mathbf M 6 nbsp 其中M i j displaystyle M i j nbsp 的計算也是使用施特拉森演算法求得 評論 编辑一般矩陣乘法的時間複雜度為O n log 2 8 O n 3 displaystyle O n log 2 8 O n 3 nbsp 施特拉森演算法因為只有每次的分治法 英語 Divide and conquer algorithm 只有七個矩陣乘法運算 所以依照主定理 英語 Master theorem 可以得出時間複雜度為O n log 2 7 O n 2 807 displaystyle O n log 2 7 O n 2 807 nbsp 但Strassen演算法的數值穩定性較差 現時時間複雜度最低的矩陣乘法演算法是Coppersmith Winograd方法的一种扩展方法 其算法复杂度为O n 2 3727 displaystyle O n 2 3727 nbsp 1 相關連結 编辑矩陣乘法参考来源 编辑 Virginia Vassilevska Williams Multiplying matrices faster than Coppersmith Winograd PDF 2014 01 14 原始内容存档 PDF 于2013 10 08 而1990年Coppersmith Winograd方法提出时的算法复杂度为O n 2 3727 displaystyle O n 2 3727 nbsp 取自 https zh wikipedia org w index php title 施特拉森演算法 amp oldid 71775363, 维基百科,wiki,书籍,书籍,图书馆,