行业知识
python实现长链矩阵的高效乘法
2026-10-31 18:24:14
来源：互联网转载
对于���阵乘法，是在各类工程实践中都会有着广泛应用的方法，但是矩阵乘法存在耗时耗力的缺点，两个相乘的矩阵C=A.B，如果A对应的列数是n，B所对应的行数是n，那么矩阵C中的一个元素的运算过程就是：
添加图片注释，不超过 140 字（可选）
矩阵C中i行j列所对应的元素等于矩阵A中的第i行的元素与矩阵B中的第j列的元素分别相乘后再相加的值，这也就可以得出矩阵C的单个元素的计算时间就为O(n)，而C中会存在n^2个元素，这也就会导致算出矩阵C的时间复杂度是3次方级别，因此得出的结论就是矩阵乘法的运算时长非常长。
添加图片注释，不超过 140 字（可选）
从上图又可以得出如果在多个矩阵相乘的时候，如果相乘的过程中使用结合律，调整矩阵相乘的次序的话，那将会有可能大大提高多个矩阵相乘的效率。
所以这里就可以考虑使用动态规划来实现多个矩阵相乘的过程，以达到提高效率的目的。而上表中的第四种矩阵相乘的次序是效率最高的，要如何通过动态规划来得到这个次序，也就是矩阵不同的乘法次序可以通过二叉树来展现假设当前有4个矩阵相乘，可以用括号来制定不同的矩阵相乘的次序，可以用二叉树来表达者两种对应乘法次序，例如：
添加图片注释，不超过 140 字（可选）
上图所示的矩阵相乘时候对应于二叉树的叶子结点，两个叶子节点的父节点对应于两个矩阵乘积后的矩阵，二叉树的根节点就是多个矩阵相乘后的最终结果。
使用python实现查找最优矩阵乘积次序的代码实现如下：
import sysN = 4 #相乘的矩阵数M = []M.append((50, 20)) #构造5.2.1节对应的4个矩阵维度M.append((20, 1))M.append((1, 10))M.append((10, 100))arrange_map = {} #记录给定i和j对应的最优分割kC = np.zeros((N, N)).astype(int)for i in range(N): for j in range(N): C[i][j] = -1def compute_c_table(C, i, j): if i = N: return if j = N: return if i == j: C[i][j] = 0 if C[i][j] != -1: #当前元素已经计算过 return C[i][j] cost = sys.maxsize best_k = i for k in range(i, j): first_part_cost = compute_c_table(C, i, k) second_part_cost = compute_c_table(C, k + 1, j) if first_part_cost + second_part_cost + M[i][0]*M[k][1]*M[j][1]
