矩阵优化递推的思想在于把递推的层数化为矩阵的幂数,也就是说设计一个矩阵 \(A\),使得 \(A^n\) 中的某个元素就是递推的第 \(n\) 项,即 \(f_n\)。这么做就可以将 \(O(n)\) 的递推优化为 \(O(\log_2 n)\)的矩阵快速幂(矩阵 \(A\) 的行列数为常数,因此快速幂中的矩阵乘法复杂度为常数),本质上是一种倍增做法
具体的讲,假如是我们现在有如下线性递推关系
\[f_n,f_{n-1},f_{n-2},\dots,f_2,f_1 \\ f_n=\{f_{n-1},f_{n-2},\dots,f_{n-k-1}\} \]其中第二行的 \(\{\}\) 代表一种运算,意味着 \(f_n\) 可以由 \(f_{n-1}\) 到 \(f_{n-k}\) 的这些数做某种运算得出
那我们将这种递推关系转化为矩阵乘法形式(\(A\) 为 \((k+1)\times(k+1)\) 的方阵),得:
\[\begin{bmatrix} f_n & f_{n-1} \dots f_{n-k} \end{bmatrix} = \begin{bmatrix} f_{n-1} & f_{n-2} \dots f_{n-k-1} \end{bmatrix} A = \begin{bmatrix} f_{n-2} & f_{n-3} \dots f_{n-k-2} \end{bmatrix} A^2 = \dots = \begin{bmatrix} f_{k} & f_{k-1} \dots f_0 \end{bmatrix} A^{n-k} \]这样,我们只需要计算到 \(f_k\) ,剩下就交给矩阵快速幂 \(O(\log_2 n)\) 计算 \(A^{n-k}\) 即可
那么,如何设计矩阵 \(A\) 呢?
我们以计算斐波拉契数列为例,首先我们可以很快得出形如上式的矩乘形式
\[\begin{bmatrix} f_n & f_{n-1} \end{bmatrix} = \begin{bmatrix} f_{n-1} & f_{n-2} \end{bmatrix} A = \dots = \begin{bmatrix} f_1 & f_0 \end{bmatrix} A^{n-1} \]那么 \(A\) 一定为一个 \(2\times2\) 的矩阵,我们令其为 \(\begin{bmatrix}a&b\\c&d\end{bmatrix}\) 代入上式 \(\begin{bmatrix}f_n & f_{n-1}\end{bmatrix}=\begin{bmatrix}f_{n-1} & f_{n-2}\end{bmatrix}A\) 得到如下:
\[\begin{bmatrix} f_n & f_{n-1} \end{bmatrix} = \begin{bmatrix} (a\cdot f_{n-1}+c\cdot f_{n-2}) & (b\cdot f_{n-1}+d\cdot f_{n-2}) \end{bmatrix} \]因此可以得到
\[f_n=a\cdot f_{n-1}+c\cdot f_{n-2}\\f_{n-1}=b\cdot f_{n-1}+d\cdot f_{n-2} \]代入 \(n\) 较小的值,手工计算出 \(f_n\),\(f_{n-1}\) 和 \(f_{n-2}\),最后得解 \(\begin{cases}a=b=c=1\\d=0\end{cases}\)
因此,\(A=\begin{bmatrix}1&1\\1&0\end{bmatrix}\)
标签:dots,begin,end,cdot,矩阵,bmatrix,递推,加速 From: https://www.cnblogs.com/SkyNet-PKN/p/17451485.html