题解 | #矩阵乘法#

矩阵乘法

http://www.nowcoder.com/practice/ebe941260f8c4210aa8c17e99cbc663b

矩阵乘法

描述

如果A是个x行y列的矩阵，B是个y行z列的矩阵，把A和B相乘，其结果将是另一个x行z列的矩阵C。这个矩阵的每个元素是由下面的公式决定的
$\begin{equation*} C_{ij} = \sum_{k=0}^{y-1}A_{ik}*B_{kj} \end{equation*} (其中0 \leq i < x, 0 \leq j < y)$
矩阵的大小不超过100*100

输入描述：
输入包含多组数据，每组数据包含：
第一行包含一个正整数x，代表第一个矩阵的行数
第二行包含一个正整数y，代表第一个矩阵的列数和第二个矩阵的行数
第三行包含一个正整数z，代表第二个矩阵的列数
之后x行，每行y个整数，代表第一个矩阵的值
之后y行，每行z个整数，代表第二个矩阵的值

输出描述：
对于每组输入数据，输出x行，每行z个整数，代表两个矩阵相乘的结果

示例1

输入：

输出：

14 13
10 11

说明：

示例2

输入：

2
2
2
1 1
1 1
1 1
1 1
16
8
7
17 19 16 19 14 1 14 9 
7 2 7 9 16 14 16 12 
13 3 3 17 5 9 8 16 
1 14 16 10 13 13 14 1 
13 13 15 4 7 2 6 16 
16 15 5 5 15 13 1 11 
11 5 0 16 14 7 7 15 
0 16 4 7 16 6 0 15 
2 14 11 2 17 17 5 12 
8 13 11 10 1 17 10 8 
15 16 17 15 7 8 13 14 
5 19 11 3 11 14 5 4 
9 16 13 11 15 18 0 3 
15 3 19 9 5 14 12 3 
9 8 7 11 18 19 14 18 
12 19 9 1 0 18 17 10 
5 18 16 19 6 12 5 
1 17 1 5 9 16 3 
14 16 4 0 19 3 6 
11 9 15 18 11 17 13 
5 5 19 3 16 1 12 
12 13 19 1 10 5 18 
19 18 6 18 19 12 3 
15 11 6 5 10 17 19

输出：

2 2
2 2
1020 1490 1063 1100 1376 1219 884
966 1035 1015 715 1112 772 920
822 948 888 816 831 920 863
855 1099 828 578 1160 717 724
745 1076 644 595 930 838 688
635 1051 970 600 880 811 846
748 879 952 772 864 872 878
526 722 645 335 763 688 748
764 996 868 362 1026 681 897
836 1125 785 637 940 849 775
1082 1476 996 968 1301 1183 953
609 987 717 401 894 657 662
700 1083 1022 527 1016 746 875
909 1162 905 722 1055 708 720
1126 1296 1240 824 1304 1031 1196
905 1342 766 715 1028 956 749

方法一

思路分析

本题方法一直接根据矩阵乘法的方法进行计算。设A为m行p列的矩阵，B为p行n列的矩阵，那么称矩阵C为矩阵A与B的乘积，其中矩阵C中的第i行第j列元素可以表示为：

$\begin{equation*} C_{ij} = \sum_{k=0}^{p}A_{ik}*B_{kj}=\sum_{k=0}^{p}a_{ik}*b_{kj}=a_{i1}*b_{1j}+a_{i2}*b_{2j}+...+a_{ip}*b_{pj} \end{equation*}$

核心代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
    int n=0,m=0,p=0;
    while(cin>>n>>m>>p)
    {
        vector<vector<int>>arr1(n+1,vector<int>(m+1,0));//存储矩阵数组
        vector<vector<int>>arr2(m+1,vector<int>(p+1,0));
        vector<vector<int>>arr3(n+1,vector<int>(p+1,0));//存储结果数组
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>arr1[i][j];
            }
        }
        for(int j=1;j<=m;j++)
        {
            for(int k=1;k<=p;k++)
            {
                cin>>arr2[j][k];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=p;j++)
            {
                for(int k=1;k<=m;k++)
                {
                    arr3[i][j]+=arr1[i][k]*arr2[k][j];//矩阵每一个位置的元素计算
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=p;j++)
                cout<<arr3[i][j]<<" ";
            cout<<endl;
        }
    }
}

复杂度分析

时间复杂度：时间主要消耗在计算矩阵的每一个位置元素，三层循环嵌套，因此时间复杂度$O(m*n*k)$，其中m，n表示第一个矩阵的行数与列数，k表示第二个矩阵的列数
空间复杂度：本方法并没有直接的额外空间的使用，因此空间复杂度为$O(1)$

方法二

思路分析

对于方法一中的三层嵌套循环求解结果矩阵的每一个元素，可以通过分析调整嵌套的次序，从而节省时间开销。进行如下调整，根据计算机内部的存取方式在访问arr3[i][j]和arr2[k][j]时不会跳跃，从而减少开销。

for(int k=1;k<=m;k++)
{
    for(int i=1;i<=n;i++)
    {
        int r=arr1[i][k];
        for(int j=1;j<=p;j++)
        {
            arr3[i][j]+=r*arr2[k][j];//矩阵计算方式
        }
    }
}

核心代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    
    int n=0,m=0,p=0;
    while(cin>>n>>m>>p)
    {
        vector<vector<int>>arr1(n+1,vector<int>(m+1,0));//存储矩阵数组
        vector<vector<int>>arr2(m+1,vector<int>(p+1,0));
        vector<vector<int>>arr3(n+1,vector<int>(p+1,0));//存储结果数组
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>arr1[i][j];
            }
        }
        for(int j=1;j<=m;j++)
        {
            for(int k=1;k<=p;k++)
            {
                cin>>arr2[j][k];
            }
        }
        for(int k=1;k<=m;k++)
        {
            for(int i=1;i<=n;i++)
            {
                int r=arr1[i][k];
                for(int j=1;j<=p;j++)
                {
                    arr3[i][j]+=r*arr2[k][j];//矩阵计算方式
                }
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=p;j++)
                cout<<arr3[i][j]<<" ";
            cout<<endl;
        }
    }
}

复杂度分析