首页 软考中级软件设计师正文

已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别

双十一,阿里云钜惠服务器,欢迎选购 双十一,阿里云钜惠服务器,欢迎选购!

已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律,如三个矩阵A、B、C相乘的顺序可以是(A*B)*C也可以是A*(B*C)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个矩阵A1A2.....An相乘的计算顺序具有最优子结构,即A1A2......An的最优计算顺序包含其子问题A1A2.....Ak和Ak+1Ak+2......An (1<k<n) 的最优计算顺序。可以列出其递归式为:
6501.png其中,Ai的维度为pi-1 *Pi,m[i,j]表示AiAi+1.....Aj最优计算顺序的相乘次数。先采用自底向上的方法求n个矩阵相乘的最优计算序。则求解该问题的算法设计策略为(  )。算法的时间复杂度为(  ),空间复杂度为(   )。给定一个实例,(p0p1......p5)= (20,15,4,10,20,25) ,最优计算顺序为(   )(2019年软件设计师上半年)
A.分治法
B.动态规划法
C.贪心法
D.回溯法


A.O(n&sup2;)
B.O(n&sup2;lgn)
C.O(n&sup3;)
D.O(2^n)


A.O(n&sup2;)
B.O(n&sup2;lgn)
C.O(n&sup3;)
D.O(2^n)


A. (((A1 *A2)*A3)*A4)*A5
B. A¡*(A2*(A3*(A4*A5)))
C. ((A¡*A2)*A3)* (A4*A5)
D. (A¡*A2) *((A3*A4)*A5)







参考答案:B  C  A  D

参考解析:

版权声明

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

本文链接:https://ruankaoti.com/post/1141.html

评论

微信扫码,获取更多

微信扫码进入小程序,获取更多软考资料