答案及解析：[填空题]已知矩阵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）的最优计算顺序。

可以列出其递归式为：

中级软件设计师,历年真题,2019年上半年（上午）《软件设计师》真题

其中，Ai的维度为pi-1*pi，m[i,j]表示AiAi+1……Aj最优计算顺序的相乘次数。
先采用自底向上的方法求n个矩阵相乘的最优计算顺序。则求解该问题的算法设计策略为（　　）。算法的时间复杂度为（　　），空间复杂度为（　　）。
给定一个实例，（p0p1……p5）=（20,15,4,10,20,25），最优计算顺序为（　　）。

问题1选项
A.分治法
B.动态规划法
C.贪心法
D.回溯法
问题2选项
A.O(n2)
B.O(n2lgn)
C.O(n3)
D.O(2^n)
问题3选项
A.O(n2)
B.O(n2lgn)
C.O(n3)
D.O(2^n)
问题4选项
A.(((A1×A2)×A3)×A4)×A5
B.A1×(A2×(A3×(A4×A5)))
C.((A1×A2)×A3)× (A4×A5)
D.(A1×A2) ×( (A3×A4)×A5)

Tags：软件水平考试中级软件设计师试题及答案

答案解析：

╋纠错

您可能感兴趣的问题