题解 | #矩阵乘法#

矩阵乘法

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

题目的主要信息:

如果A是个x行y列的矩阵,B是个y行z列的矩阵,要求计算A和B相乘得到的x行z列的矩阵C。

方法一:

如果A是个x行y列的矩阵,B是个y行z列的矩阵,矩阵C为矩阵A与B的乘积,其中矩阵C中的第i行第j列元素可以表示为:

Cij=k=1yAik×BkjC_{ij}=\sum_{k=1}^yA_{ik}\times B_{kj}

用一个三重循环实现这个公式。最后再输出C。 alt

具体做法:

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int x, y, z;
    while (cin >> x >> y >> z){
        vector<vector<int>> A(x, vector<int>(y, 0));
        vector<vector<int>> B(y, vector<int>(z, 0));
        vector<vector<int>> C(x, vector<int>(z, 0));
        for(int i = 0; i < x; ++i){//输入矩阵A
            for(int j = 0; j < y; ++j)
                cin >> A[i][j];
        }
        for(int i = 0; i < y; ++i){//输入矩阵B
            for(int j = 0; j < z; ++j)
                cin >> B[i][j];
        }
        for(int i = 0; i < x; ++i){//计算C[i][j]的值
            for(int j = 0; j < z; ++j)
                for(int k = 0; k < y; ++k)//A的第i行和B的第j列相乘的结果为C[i][j]
                    C[i][j] += A[i][k] * B[k][j];
        }
        for(int i = 0; i < x; ++i){//输出C
            for(int j = 0; j < z-1; ++j)
                cout << C[i][j] << " ";
            cout << C[i][z-1] << endl;
        }
    }
    return 0;
}

复杂度分析:

  • 时间复杂度:O(xyz)O(xyz),三重for循环计算C中的值。
  • 空间复杂度:O(1)O(1),只用了常数空间。

方法二:

改变三重for循环的顺序,从逐个值计算变为逐行计算,可以加快程序运行的速度。

具体做法:

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int x, y, z;
    while (cin >> x >> y >> z){
        vector<vector<int>> A(x, vector<int>(y, 0));
        vector<vector<int>> B(y, vector<int>(z, 0));
        vector<vector<int>> C(x, vector<int>(z, 0));
        for(int i = 0; i < x; ++i){//输入矩阵A
            for(int j = 0; j < y; ++j)
                cin >> A[i][j];
        }
        for(int i = 0; i < y; ++i){//输入矩阵B
            for(int j = 0; j < z; ++j)
                cin >> B[i][j];
        }
        for(int i = 0; i < x; ++i){
            for(int j = 0; j < y; ++j){
                for(int k = 0; k < z; ++k){//计算C第i行的值
                    C[i][k] += A[i][j] * B[j][k];
                }
            }
        }
        for(int i = 0; i < x; ++i){//输出C
            for(int j = 0; j < z-1; ++j)
                cout << C[i][j] << " ";
            cout << C[i][z-1] << endl;
        }
    }
    return 0;
}

复杂度分析:

  • 时间复杂度:O(xyz)O(xyz),逐行计算,三重for循环计算C中的值。
  • 空间复杂度:O(1)O(1),只用了常数空间。
全部评论

相关推荐

但听说转正率很低,我现在有在实习了,好纠结要不要去
熬夜脱发码农:转正率低归低,但是实习的经历你可以拿着,又不是说秋招不准备了
点赞 评论 收藏
分享
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务