完善了算法导论,值得一看.多线程算法(完整版) ——算法导论第 3 版新增第 27 章 矩阵相乘的多线程分治算法 如 4.2 节中所讲,可以采用 Strassen 分治策略在 Θ(nlg7 )= Θ(n2.81 ) 的时间内串行地完成 n×n 矩阵的相乘,这激发我们去寻找该算法的多线程版本。和 4.2 节中一样,我们先来多线程化一个简单一些的分治算法。 回忆一下第 77 页中的 SQUARE-MATRIX-MULTIPLY-RECURSIVE 过程,它把两个 n×n 矩阵 A 、 B 相乘得到一个 n×n 矩阵 C ,采用的方法是把这三个矩阵都分割成四个 n/2×n/2 的子矩阵: A={{A11 ,A12 },{ A21 ,A22 }}, B={{B11 ,B12 },{ B21 ,B22 }}, C={{C11 ,C12 },{ C21 ,C22 }} 。 我们可以把矩阵积记为: {{C11 ,C12 },{ C21 ,C22 }} = {{A11 ,A12 },{ A21 ,A22 }} * {{B11 ,B12 },{ B21 ,B22 }} = {{A11 B11 , A11 B12 },{ A21 B11 , A21 B12 }} + {{A12 B21 , A12 B22 },{ A22 B21 , A22 B22 }} (27.6)