我要招人

去企业版

首页 > 试题广场 >

计算三个稠密矩阵 A、B、C 的乘积 ABC，假定三个矩阵的

[单选题]

计算三个稠密矩阵 A、B、C 的乘积 ABC，假定三个矩阵的尺寸分别为 m*n, n*p,p*q，且 m<n<p<q,以下计算效率最高的是

```
(AB)C
```
```
A(BC)
```
```
(AC)B
```
```
(BC)A
```
```
(CA)B
```

推荐

zero

a*b,b*c两矩阵相乘效率为a*c*b ABC=(AB)C=A(BC).

(AB)C = m*n*p + m*p*q,A(BC)=n*p*q + m*n*q.

m*n*p<m*n*q,m*p*q<n*p*q,所以(AB)C最小

编辑于 2015-01-26 20:16:58 回复(1)

Miner_Sty

根据简单的矩阵知识，可以排除后面四项，因为A*B，A的列数必须和B的行数相等。

• 再看选项1和选项2，如下图所示，一个m*n的矩阵A乘以n*q的矩阵B。我们会用矩阵A的第一行，乘以矩阵B的第一列并相加。这一运算需要耗费n次乘法以及n-1次加法，矩阵B有q列，矩阵A有m行，所以A*B的复杂度为m*(2n-1)*q。

• 根据上面的分析，我们可以知道选项1的复杂度为m*(2n-1)*p + m*(2p-1)*q，而选项2的复杂度为m*(2n-1)*q+ n*(2p-1)*q，很显然选项1的效率高于选项2。

发表于 2015-04-01 15:25:17 回复(2)

牛客-007

答案：A

首先矩阵相乘一般是不能交换顺序的，所以选项CDE就是错误的。

首先使较小的矩阵相乘，最后乘较大的矩阵可以减少运算量。所以B选项的效率最高

编辑于 2015-03-21 10:43:21 回复(3)

牛客吴彦祖QAQ

发表于 2017-09-24 17:20:02 回复(0)

666的佩奇爸爸

答案：A。

根据矩阵运算知识，可以排除选项C与选项D，因为矩阵A与矩阵B相乘，矩阵A的列数必须与矩阵B的行数相等。

对于选项A与选项B，一个m*n的矩阵A乘以n*q的矩阵B，会用矩阵A的第一行，乘以矩阵B的第一列并相加。这一运算需要耗费n次乘法以及n-1次加法，矩阵B有q列，矩阵A有m行，所以，A*B的复杂度为m*(2n-1)*q。

根据上面的分析可知，选项A的复杂度为m*(2n-1)*p + m*(2p-1)*q，而选项B的复杂度为m*(2n-1)*q+ n*(2p-1)*q，很显然，选项A的效率高于选项B。所以，选项A正确。

发表于 2018-07-15 11:39:19 回复(0)

心灵交战

（ 1 ） a*b 矩阵和 b*c 矩阵相乘，每次行乘列运算需要 b 次乘法和 b-1 次加法，即总共需要 (2b-1)*a*c 次运算，时间复杂度为 O(a*b*c)

（ 2 ）对于 (AB)C 而言：

1.AB 的时间复杂度为 O(m*n*p) ，此时形成 m*p 的新矩阵

2.(AB)C 的时间复杂度为 O(m*p*q)

（ 3 ）对于 A(BC) 而言：

1.BC 的时间复杂度为 O(n*p*q) ，此时形成 n*q 的新矩阵

2.A(BC) 的时间复杂度为 O(m*n*q)

发表于 2016-04-07 09:36:50 回复(1)

认真的徐同学

(AB)C 要mp(2n-1)+mq(2p-1)次运算;
A(BC) 要nq(2p-1) mq(2n-1)次运算；

又因为m<n<p<q;所以

mp(2n-1)<mq(2n-1);
mq(2p-1)<nq(2p-1);

所以(AB)C运算次数最少，效率最高；越小越要先乘

发表于 2017-09-10 14:04:18 回复(1)

斯特恩

C,D,E显然都是错的,不论这些矩阵是否能那样乘,乘出来的结果都无法保证和ABC相等
只有A,B这两种计算次序能产生正确结果
A的计算量是2mnp+2mpq,B的计算量是2npq+2mnq,两者相减可得A的计算量教小
这里假定“效率”直接由计算量决定

发表于 2017-07-28 16:51:57 回复(0)

huixieqingchun

根据矩阵的乘法，要具体运算算法的时间复杂度。

发表于 2016-05-13 12:41:35 回复(0)

梦云儿

qqqq

发表于 2015-09-25 19:46:05 回复(0)

ttkl

题目漏写p<q的关系，C、D、E无法相乘，比较A、B选项即可

发表于 2015-01-26 13:49:48 回复(3)

提交观点

问题信息

贪心复杂度阿里巴巴

来自：阿里巴巴2015研发工...

难度：

11条回答 607收藏 30935浏览

计算三个稠密矩阵 A、B、C 的乘积 ABC，假定三个矩阵的

问题信息

热门推荐

相关试题