快速幂是一个非常常见的优化,其将$ O(n) $的乘法优化到了$ O(\log{n}) $的级别,加快了幂运算的速度,代码实现起来也非常简单。

fast_pow( a int, b int ) {
    ret := 1;
      for ( ; b; b >>= 1 ) {
        if ( b & 1 ) 
        ret *= a;
        a *= a;
    }
  
    return ret;
}

我们都知道,快速幂的原理是利用二进制拆分指数$b$,使其形成$a^b=a^1\times a^2\times a^4...$的形式从而减少了冗余的乘法运算,那么对于同样形式的矩阵乘法$A^b$,我们是否也能采用同样的方法减少运算次数呢?答案是可以的。

斐波那契数列

斐波那契数列形如$1,1,2,3...$,其从$n=3$开始的每一项都是前两项的和,通常情况下,计算前$n$项的时间复杂度为$O(n)$,这仍然具有优化的空间。

考虑下面两个个矩阵乘法:

$$ \left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]\left[\begin{matrix}A\\B\end{matrix}\right]=\left[\begin{matrix}A+B\\A\end{matrix}\right] $$

$$ \left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]\left[\begin{matrix}A+B\\A\end{matrix}\right]=\left[\begin{matrix}2A+B\\A+B\end{matrix}\right] $$

我们可以发现,只要不断对原矩阵左乘一个转移矩阵$A=\left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]$,我们恰好就可以得到一个斐波那契数列,如果需要求第$b$项,我们要求的恰好就是$A^b$左乘原矩阵$\left[\begin{matrix}A\\B\end{matrix}\right]$。

矩阵快速幂

求矩阵幂?为什么我们不可以采用和快速幂一样的思路,将$A^b$拆分成$A^1\times A^2\times A^4...$的形式呢?

matrix_fast_pow( int a, int b ) {
    ret matrix
      for ( ; b; b >>= 1 ) {
        if ( b & 1 ) 
        ret := matrix_multiply(ret, a);
        a := matrix_multiply(a, a);
    }
  
    return ret;
}

由此,我们用矩阵快速幂将求斐波那契数列的时间复杂度降低到了$O(\log{n})$的级别。

Last modification:August 8th, 2020 at 11:38 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏