软题库 培训课程
当前位置:信管网 >> 在线考试中心 >> 软件设计师题库 >> 试题查看
试卷年份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

查看答案

相关试题