首页 软件设计师正文

两个矩阵Am*n和Bn*p相乘,用基本的方法进行,则需要的乘(2016年下半年软件设计师上午综合知识真题解析)

两个矩阵 Am*n 和 Bn*p 相乘,用基本的方法进行,则需要的乘法次数为 m*n*p。多个矩阵相乘满足结合律,不同的乘法顺序所需要的乘法次数不同。考虑采用动态规划方法确定Mi,M(i+i),…,Mj 多个矩阵连乘的最优顺序,即所需要的乘法次数最少。最少乘法次数用 m[i,j]表示,其递归式定义为:

其中 i、 j 和 k 为矩阵下标,矩阵序列中 Mi 的维度为(Pi-1.)*Pi 采用自底向上的方法:实现该算法来确定 n 个矩阵相乘的顺序,其时间复杂度为(  )。若四个矩阵 M1、 M2、 M3、M4相乘的维度序列为 2、 6、 3、 10、3,采用上述算法求解,则乘法次数为(  )。
A.O(N2
B.O(N2Lgn)
C.O(N3
D.O(n3lgn)
A.156
B.144
C.180
D.360






参考答案: C、B
参考解析:正在整理中,欢迎在文下评论区提供答案解析,谢谢!
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。

本文链接:https://scpro.cn/v/64291006b82411ee.html

相关文章