当前位置:首页计算机类软件水平考试中级软件设计师->已知矩阵Am*n和Bn*p相乘的时间复杂度为O(mnp)。矩

已知矩阵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)

查看答案 纠错
答案: BCAD
本题解析: 暂无解析
更新时间:2021-12-13 10:49

你可能感兴趣的试题

单选题

(  )is the process of transforming information so it is unintelligible to anyone but the intended recipient.

  • A.Encryption
  • B.Decryption
  • C.Security
  • D.Protection
查看答案
单选题

As each application module is completed,it undergoes(  )to ensure that it operates correctly and reliably.

  • A.unit testing
  • B.integration testing
  • C.system testing
  • D.acceptance testing
查看答案
单选题

(  )algorithm specifies the way to arrange data in a particular order.

  • A.Search
  • B.Random
  • C.Sorting
  • D.Merge
查看答案
单选题

After analyzing the source code,(  )generates machine instructions that will carry out the meaning of the program at a later time.

  • A.an interpreter
  • B.a linker
  • C.a compiler
  • D.a converter
查看答案
单选题

(  )can help organizations to better understand the information contained within the data and will also help identify the data that is most important to the business and future business decisions.

  • A.Data processing system
  • B.Big Data analytics
  • C.Cloud computing
  • D.Database management
查看答案
单选题

浏览器开启无痕浏览模式后,(  )依然会被保存下来。

  • A.浏览历史
  • B.搜索历史
  • C.已下载文件
  • D.临时文件
查看答案
单选题

下列协议中,不属于TCP/IP协议簇的是(  )。

  • A.CSMA/CD
  • B.IP
  • C.TCP
  • D.UDP
查看答案
单选题

下列传输介质中,带宽最宽、抗干扰能力最强的是(  )。

  • A.双绞线
  • B.红外线
  • C.同轴电缆
  • D.光纤
查看答案
单选题

数控编程常需要用参数来描述需要加工的零件的图形。在平面坐标系内,确定一个点需要2个独立的参数,确定一个正方形需要(  )个独立的参数。

  • A.3
  • B.4
  • C.5
  • D.6
查看答案
单选题

某书的页码为1,2,3,...,共用数字900个(一个多位数页码包含多个数字),据此可以推断,该书最大的页码为(  )。

  • A.237
  • B.336
  • C.711
  • D.900
查看答案