矩阵乘法

题意

计算 $n\times m$ 矩阵 $A$ 与 $m\times k$ 矩阵 $B$ 的乘积。

思路

结果的第 $i,j$ 项是 A[i] 与 $B$ 的第 $j$ 列对应元素乘积之和。外层枚举 $A$ 的行和结果列，内层枚举公共维度。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <cstdio>

int n,m,k;
int a[200][200];
int b[200][200];
int c[200][200];
int main(){
    int i,j;
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for (i=1;i<=m;i++){
        for (j=1;j<=k;j++){
            scanf("%d",&b[i][j]);
        }
    }
    int x,y;
    for (i=1;i<=n;i++){
        for (j=1;j<=k;j++){
            for(x=1;x<=m;x++){
                c[i][j] += a[i][x]*b[x][j];
            }
            printf("%d ",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

复杂度

总结

Python代码

python

1
2
3
4
5
6row_count, shared_count, column_count = map(int, input().split())
first = [list(map(int, input().split())) for _ in range(row_count)]
second = [list(map(int, input().split())) for _ in range(shared_count)]

for row in first:
    print(*(sum(row[index] * second[index][column] for index in range(shared_count)) for column in range(column_count)))

C++代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#include <cstdio>

int n,m,k;
int a[200][200];
int b[200][200];
int c[200][200];
int main(){
    int i,j;
    scanf("%d%d%d",&n,&m,&k);
    for (i=1;i<=n;i++){
        for (j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for (i=1;i<=m;i++){
        for (j=1;j<=k;j++){
            scanf("%d",&b[i][j]);
        }
    }
    int x,y;
    for (i=1;i<=n;i++){
        for (j=1;j<=k;j++){
            for(x=1;x<=m;x++){
                c[i][j] += a[i][x]*b[x][j];
            }
            printf("%d ",c[i][j]);
        }
        printf("\n");
    }
    return 0;
}

复杂度

时间复杂度为 $O(nmk)$ ，输入矩阵空间为 $O(nm+mk)$ 。

总结

矩阵乘法不是对应相乘，而是“一行乘一列”的内积。

目录

题意

思路

代码

复杂度

总结

Python代码

C++代码

复杂度

总结