已知矩阵Amn和Bnp相乘的时间复杂度为O(mnp)。矩阵相乘满足结合律，如三个矩阵A、B、C相乘的顺序可以是(AB)C也可以是A(BC)。不同的相乘顺序所需进行的乘法次数可能有很大的差别。因此确定n个矩阵相乘的最优计算顺序是一个非常重要的问题

admin2020-08-10 56

问题已知矩阵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 (l<=k可以列出其递归式为：

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

选项 A、分治法
B、动态规划法
C、贪心法
D、回溯法

答案B

解析

转载请注明原文地址:https://kaotiyun.com/show/DUCZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

[说明]下面是一个Appkt程序，其功能是从3～100之间(包括3和100)每隔0.5秒显示一个新的数字，如果数字为素数，则显示为灰色，其他为绿色。程序运行结果如图4所示。importjava.awt.*

在程序流程图(见图6-21)中，若要某个房间I被选中，则需要满足什么条件?假设该旅馆当前各个房间的情况如表6-14所示。当输入M=3，R=0时，该算法的输出是(1)。当输入M=2，R=1时，该算法的输出是(2)。

男，2岁半，因发热18小时，咳嗽，半小时前突然抽搐一次来诊，查体，T39.5℃，神清，面色潮红，前囟已闭，咽部充血，颈软，心肺腹(－)，无脑征，临床诊断为上感，高热惊厥，应给予的及时处理是

含铁多且易于吸收利用的辅食有

患者，女，21岁。食鱼虾后皮肤出现片状风团，瘙痒异常。治疗取神阙穴，所用的方法是

企业在提取法定盈余公积金前不得向投资者分配利润。()

下列不属于纯粹风险的是(　　)。

在计算个人所得税时，下列各项中不符合个体工商户有关规定的是()。

()也称期限错配风险，是最主要和最常见的利率风险形式。

近年来，嘉兴精心打造“越韵吴风，红船绿城”和“烟雨南湖，运河古城”的旅游品牌，促进了旅游经济的快速增长。全市现在已有()。

处罚法定原则要求行政处罚必须依法进行。()

软件设计师上午基础知识考试

软考中级

[说明]下面是一个Appkt程序，其功能是从3～100之间(包括3和100)每隔0.5秒显示一个新的数字，如果数字为素数，则显示为灰色，其他为绿色。程序运行结果如图4所示。importjava.awt.*

在程序流程图(见图6-21)中，若要某个房间I被选中，则需要满足什么条件?假设该旅馆当前各个房间的情况如表6-14所示。当输入M=3，R=0时，该算法的输出是(1)。当输入M=2，R=1时，该算法的输出是(2)。

男，2岁半，因发热18小时，咳嗽，半小时前突然抽搐一次来诊，查体，T39.5℃，神清，面色潮红，前囟已闭，咽部充血，颈软，心肺腹(－)，无脑征，临床诊断为上感，高热惊厥，应给予的及时处理是

含铁多且易于吸收利用的辅食有

患者，女，21岁。食鱼虾后皮肤出现片状风团，瘙痒异常。治疗取神阙穴，所用的方法是

企业在提取法定盈余公积金前不得向投资者分配利润。()

下列不属于纯粹风险的是( )。

在计算个人所得税时，下列各项中不符合个体工商户有关规定的是()。

()也称期限错配风险，是最主要和最常见的利率风险形式。

近年来，嘉兴精心打造“越韵吴风，红船绿城”和“烟雨南湖，运河古城”的旅游品牌，促进了旅游经济的快速增长。全市现在已有()。

处罚法定原则要求行政处罚必须依法进行。()

下列不属于纯粹风险的是(　　)。