题目分析

1. 题目给出了我们两个矩阵M,N，输入分别为
   • M矩阵的行数x
   • M矩阵的列数，即N矩阵的行数y
   • N矩阵的列数z
   • M矩阵的具体内容，按行输入
   • N矩阵的具体内容，按行输入 2.输出最终的乘积矩阵

方法一：根据计算规则顺序计算

• 实现思路
  • 对于矩阵计算我们有如下规则
  $Q_{ij}=\sum _{k=1}^y{M}_{ij}\times N_{kj}Q\_\{ij\}\; =\; \backslash sum\_\{k=1\}^y\; M\_\{ij\}\times N\_\{kj\}$
  • 根据这个规则来编写代码即可

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
	int x,y,z;
	while(cin>>x>>y>>z) {
		vector<vector<int>> M(x,vector<int>(y));
		vector<vector<int>> N(y,vector<int>(z));
		for(int i=0;i<x;i++) {                // 录入第一个矩阵
			for(int j=0;j<y;j++) {
				cin>>M[i][j];
			}
		}
		for(int i=0;i<y;i++) {                // 录入第二个矩阵
			for(int j=0;j<z;j++) {
				cin>>N[i][j];
			}
		}
		for(int i=0;i<x;i++) {                // 第三个矩阵的大小x*z进行遍历
			for(int j=0;j<z;j++) {
				int val=0;
				for(int r=0;r<y;r++) {        // 计算对应位置的结果
					val+=M[i][r]*N[r][j];
				}
				cout<<val<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}

复杂度分析

• 时间复杂度：$O(xyz)O(xyz)$，其中x是M的行数，y是M的列数，z是N的列数
• 空间复杂度：$O(xy+yz)O(xy+yz)$，两个辅助矩阵的空间开销

方法二：cache友好的计算顺序

• 实现思路

  • 由于计算机高速缓存的读取的机制，在一个二维数组中我们尽可能地按照地址的顺序进行每一个元素的读写是对于cache友好的，因此重新编排计算的顺序可以有一定的优化提升

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
	int x,y,z;
	while(cin>>x>>y>>z) {
		vector<vector<int>> M(x,vector<int>(y));
		vector<vector<int>> N(y,vector<int>(z));
        vector<vector<int>> Q(x,vector<int>(z));
		for(int i=0;i<x;i++) {                // 录入第一个矩阵
			for(int j=0;j<y;j++) {
				cin>>M[i][j];
			}
		}
		for(int i=0;i<y;i++) {                // 录入第二个矩阵
			for(int j=0;j<z;j++) {
				cin>>N[i][j];
			}
		}
        for(int i = 0; i < x; ++i){            
            for(int j = 0; j < y; ++j){
                int val = M[i][j];            // 获得M中的一个位置的数据val
                for(int k = 0; k < z; ++k){   // 对所有需要和val进行运算的一次性算完，并且对于N来说是cache友好的访问方式
                    Q[i][k] += val * N[j][k];
                }
            }
        }
        for(int i=0;i<x;i++) {
            for(int j=0;j<z;j++)
                cout<<Q[i][j]<<" ";
            cout<<endl;
        }
	}
	return 0;
}

复杂度分析

• 时间复杂度：$O(xyz)O(xyz)$，其中x是M的行数，y是M的列数，z是N的列数
• 空间复杂度：$O(xy+yz+xz)O(xy+yz+xz)$，三个辅助矩阵的空间开销