题解 | #矩阵乘法#

题目描述
给定两个n * n的矩阵 A和 B，求A * B。

方法一：暴力解法

求解思路
求解矩阵A和B相乘，我们直接根据矩阵乘法的定义，行列元素对应相乘后相加，即可得到本题的答案。

图片说明

解题代码

class Solution {
public:
    vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
        int n = a.size(); // 存储矩阵大小
        vector<vector<int>> myans(n, vector<int>(n)); // 用于存储结果
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                for(int k = 0; k < n; k++)
                {
                    myans[i][j] += a[i][k] * b[k][j]; // 行列元素对应相乘后相加
                }
         return myans; // 返回结果
    }
};

复杂度分析
时间复杂度：使用三重循环，因此时间复杂度为 $O$ ( $图片说明$ )
空间复杂度：使用辅助数组ans[n][n]，因此空间复杂度为 $O$ ( $图片说明$ )

方法二：优化求解

求解思路
对于本题我们可以在时间上对代码进行优化。首先我们知道二维数组在内存中是按照一维顺序进行读取的，因此我们在方法一的基础上，通过调整数组的读取顺序来进行优化，使得矩阵A和B顺序读取，然后相继送入CPU中进行计算，最后使得运行时间能够更快。

图片说明

解题代码

class Solution {
public:
    vector<vector<int> > solve(vector<vector<int> >& a, vector<vector<int> >& b) {
        int n = a.size(); // 记录矩阵的大小
        int myres; // 记录结果
        vector<vector<int> > myans(n, vector<int>(n)); // 用于存储结果
        for(int i = 0; i < n; i++)
            for(int k = 0; k < n; k++)
            {
                myres = a[i][k]; // 进行空间层次的优化
                for(int j = 0; j < n; j++)
                {
                    myans[i][j] += myres * b[k][j]; // 行列元素对应相乘后相加
                }
            }
         return myans; // 返回结果
    }
};

复杂度分析
时间复杂度：使用三重循环，因此时间复杂度为 $O$ ( $图片说明$ )，但是通过优化CPU读取数组的速度，因此对于一般的程序，方法二的代码会运行得更快。
空间复杂度：使用辅助数组ans[n][n]，因此空间复杂度为 $O$ ( $图片说明$ )