已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)矩阵相乘满足结合律,如三个矩阵
A、
B、C相乘的顺序可以是(A*
B)*
C),也可以是A*(B*
C).不同的相乘序所需进行的乘法次数可能有很大的差别,因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题。已知确定n个短阵A,A2........An相乘的计算顺序具有最优子结构,即A1A2..........An的最优计算顺序包含其子问题A1A2.......Ak和Ak+1Ak+2.......An(＜=kcn)的最优计算顺序。
可以列出其递归式为
其中,A的维度为pi-1*pim【i,j】,表示AiAi+1…Aj最优计算顺字的相乘次数,
先釆用自底向上的方法求n个矩阵相乘的最优计算顺序。则该问题的算法设计策略为(),算法的时间复杂度为(),空间复杂度为(请作答此空)
给定一个实例,(POPi........P5)=(20.15.4.10.20.25)最优计算顺序为()
A.O（n^2） B.O（n*2lgn） C.O（n^3） D.O（2n）正确答案A
