信管网试题内容

试题内容

两个矩阵 A_m*n 和 B_n*p 相乘，用基本的方法进行，则需要的乘法次数为 m*n*p。多个矩阵相乘满足结合律，不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定M_i,M_（i+i），…，M_j 多个矩阵连乘的最优顺序，即所需要的乘法次数最少。最少乘法次数用 m[i，j]表示，其递归式定义为：

其中 i、 j 和 k 为矩阵下标，矩阵序列中 M_i 的维度为（P_i-1.）*P_i 采用自底向上的方法:实现该算法来确定 n 个矩阵相乘的顺序，其时间复杂度为（  ）。若四个矩阵 M₁、 M₂、 M_3、M₄相乘的维度序列为 2、 6、 3、 10、3，采用上述算法求解，则乘法次数为（  ）。
A．O（N²）
B．O（N²Lgn）
C．O（N³）
D．O（n³lgn）
A．156
B．144
C．180
D．360