在前一篇文章《从快速幂到矩阵快速幂》中介绍了一种$O(\log n)$求解斐波那契数列的方法,其中使用的就是矩阵快速幂。

而使用矩阵快速幂的前提就是将递推式转为矩阵乘法的形式,例如前文所提到的斐波那契数列:

$$ f(n)=f(n-1)+f(n-2) $$

就可以转换为一下矩阵乘法的形式:

$$ \left[\begin{matrix}1 & 1\\1 & 0\end{matrix}\right]\left[\begin{matrix}f(n-1)\\f(n-2)\end{matrix}\right]=\left[\begin{matrix}f(n)\\f(n-1)\end{matrix}\right] $$

那么对于其他更加特殊的递推式,我们需要如何改写呢?这需要一定的数学直觉

例如对于下式:

$$ f(n)=f(n-1)+f(n-3) $$

我们可以观察,其当前项依赖于前一项和前三项之和,对此,我们可以进行如下改写:

$$ \left[\begin{matrix}1 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\end{matrix}\right]\left[\begin{matrix}f(n-1)\\f(n-2)\\ f(n-3)\end{matrix}\right]=\left[\begin{matrix}f(n)\\f(n-1)\\f(n-2)\end{matrix}\right] $$

再增加一点难度:

$$ f(n)=2f(n-1)+f(n-3)+n-3 $$

其可以改写为:

$$ \left[\begin{matrix}2 & 0 & 1 & 1 & 0\\1 & 0 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 1\\0 & 0 & 0 & 0 & 1\end{matrix}\right]\left[\begin{matrix}f(n-1)\\f(n-2)\\f(n-3)\\n-3\\1\end{matrix}\right]=\left[\begin{matrix}f(n)\\f(n-1)\\f(n-2)\\n-2\\1\end{matrix}\right] $$

注意,在改写的时候要注意不能将变量写成恒等的形式,例如这样是不行的:

$$ \left[\begin{matrix}1 & 0\\0 & 1\end{matrix}\right]\left[\begin{matrix}f(n)\\f(n-1)\end{matrix}\right]=\left[\begin{matrix}f(n)\\f(n-1)\end{matrix}\right] $$

很粗暴的来说,不能直接让左右两个列向量中某元素直接相等(常量除外)。

对于含有指数的递推式:

$$ f(n)=f(n-1)+3^n $$

我们可以可以这样处理

$$ \left[\begin{matrix}1 & 1\\0 & 3\end{matrix}\right]\left[\begin{matrix}f(n-1)\\3^n\end{matrix}\right]=\left[\begin{matrix}f(n)\\3^{n+1}\end{matrix}\right] $$

Last modification:October 29th, 2020 at 10:57 am
博客维护不易,如果你觉得我的文章有用,请随意赞赏