为什么 两个n阶矩阵相乘所需的运算次数为n的3次方?

发布网友 发布时间：2022-08-16 16:28

我来回答

共3个回答

热心网友 时间：2023-10-08 15:46

n阶矩阵相乘后得到的还是n阶矩阵，所以结果中就有n平方个元素，每个元素都是由2n个数两两相乘得到，即n次运算。所以是n的三次方

热心网友 时间：2023-10-08 15:47

AB=?C
设A=[a1
a2
...
an]（行向量组）,B=[b1 b2 ... bn]（每个向量是n维）
则：C的第i行数值为
ai*[b1 b2 ... bn](i=1..n),则有n个ai*bj(j=1..n),每一个 ai*bj有n个对应相乘的分量积，因此需要n-1次加法，得到ai*bj=Cij.
所以得到C的一行数值，需要n(n-1)阶的时间，
因为ai（i=1,2,..,n）有n个行向量，所以计算矩阵乘法AB，需要
n*(n(n-1))阶次数。

热心网友 时间：2023-10-08 15:47

for i=1:n
for j=1:n
s=0;
for k=1:n
s=s+a(i,j)*b(j,i);
end;
c(i,j)=s;
end;
end;
看到了吧！
s=s+a(i,j)*b(j,i);
这条语句就是O(n^3)
而c(i,j)=s;是O(n^2)，那么当然就是O(n^3)啦！

热心网友 时间：2023-10-08 15:46

n阶矩阵相乘后得到的还是n阶矩阵，所以结果中就有n平方个元素，每个元素都是由2n个数两两相乘得到，即n次运算。所以是n的三次方

热心网友 时间：2023-10-08 15:47

AB=?C
设A=[a1
a2
...
an]（行向量组）,B=[b1 b2 ... bn]（每个向量是n维）
则：C的第i行数值为
ai*[b1 b2 ... bn](i=1..n),则有n个ai*bj(j=1..n),每一个 ai*bj有n个对应相乘的分量积，因此需要n-1次加法，得到ai*bj=Cij.
所以得到C的一行数值，需要n(n-1)阶的时间，
因为ai（i=1,2,..,n）有n个行向量，所以计算矩阵乘法AB，需要
n*(n(n-1))阶次数。

热心网友 时间：2023-10-08 15:47

for i=1:n
for j=1:n
s=0;
for k=1:n
s=s+a(i,j)*b(j,i);
end;
c(i,j)=s;
end;
end;
看到了吧！
s=s+a(i,j)*b(j,i);
这条语句就是O(n^3)
而c(i,j)=s;是O(n^2)，那么当然就是O(n^3)啦！