矩阵乘法

发布时间 2023-11-16 21:50:12作者: peng1984729

一个神奇的东西

矩阵乘法重载符实现代码:

node operator *(const node &a)const{
        node sum(0);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                   sum.g[i][j]+=g[i][k]*a.g[k][j];
        return sum;
    }

简单来说,我们可以将加法转化为矩阵乘法,以此来达到一些优化操作(尤其是针对递推式时)。

斐波那契数列:

F1=F2=1.

Fn =Fn1+Fn2   (n3)  .

转换为:

求An就是求A1*Bn

于是就可以使用快速幂求得Bn

时间复杂度O(log n)。

注:

1.矩阵乘法不满足交换律。

2.矩阵乘法满足分配律与结合律。

3.单位矩阵(类似乘法中的1):

1 0 0 0 
0 1 0 0 
0 0 1 0 
0 0 0 1