首页 > 代码库 > 分治法实现两个方阵相乘
分治法实现两个方阵相乘
A、B是两个n*n的矩阵，计算C=A*B。
传统算法：
按照下面公式计算，需要n3次乘法和n3-n2次加法，时间复杂度为Θ(n3)。
递归算法：
假定n为2的幂，将A、B、C分成4个大小为(n/2)*(n/2)的子矩阵。
用分治法来计算C。
需要8次(n/2)*(n/2)矩阵的乘法和4次(n/2)*(n/2)矩阵的加法，其中乘法是原来的1/8倍消费，加法是原来的1/4倍耗费。用m表示n=1是乘法的耗费，用a表示加法的耗费。
于是有了下面的递推式：
可以推出：
同样需要n3次乘法和n3-n2次加法，与传统方法相比，时间复杂度没有改进，反而还增加了递归带来的管理开销。
Strassen算法：
复杂度为o(n3)，运行时间渐进少于n3。
像递归方法一样划分矩阵，但在计算C的时候有一些不同。
首先计算出一些中间值：
再由这些中间值得出C：
Strassen算法进行了18次加法和7次乘法。对于运行时间有如下的递推式：
经过计算可得，运行时间为Θ(nlog7)=O(n2.81)。
三个算法的比较：
#include<iostream> #include<stdio.h> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int dim=20; //最高的维度,可调 int mod=1000000007; // 结果取的模,可调 int mk=5;// 运算时是运算几维矩阵的,可调 struct Matrix { ll a[dim][dim]; Matrix(){memset(a,0,sizeof(a));} }; Matrix operator *(const Matrix& a,const Matrix& b) { Matrix ret; for(int i=0;i<mk;++i) for(int j=0;j<mk;++j) for(int k=0;k<mk;++k) { ret.a[i][j]+=a.a[i][k]*b.a[k][j]; ret.a[i][j]%=mod; } return ret; } Matrix operator ^(Matrix x, ll n) { Matrix ret; for(int i=0;i<mk;++i)ret.a[i][i]=1; while(n) { if(n&1)ret=ret*x; x=x*x; n>>=1; } return ret; } int main() { int a; cin>>a; }
分治法实现两个方阵相乘
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。