当前位置：首页 > news >正文

「数学::快速幂」矩阵快速幂运算|快速斐波那契数列 / LeetCode 509（C++）

news 2024/10/22 15:29:59

概述

思路

算法过程

复杂度

Code

概述

LeeCode 509：

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

我们介绍过快速幂运算：「数学::快速幂」基本快速幂运算|快速幂取模运算（C++）
快速幂不仅可以用于求数的幂，也可以求矩阵的幂，进而进行将一些递推算法优化成logn算法。

思路

我们首先要求你掌握一些线性代数知识：矩阵的乘法。

矩阵（Matrix）是一个按照方阵排列的复数或实数集合。

矩阵乘法： {

A(mn)*B(st)=C(mt)，一个m行n列的矩阵A乘以一个s行t列的矩阵B等于一个m行t列的矩阵的C。

其中，我们要求n必须等于s，否则无法相乘。

接下来我们称矩阵的i行j列为[i][j]。

$\sum$ A[i][k]*B[k][j]=C[i][j] ( $\sum$ :枚举k从1到n)

即：C[i][j]的元素等于A的i行每个元素与B的j行每个对应元素的积的累加和：

      ┌ 2 1 ┐ * ┌ 1 0 ┐ = ┌ 3 3 ┐└ 0 1 ┘   └ 1 3 ┘   └ 1 3 ┘

A矩阵的行数与B矩阵的列数是可以不相等的：

                ┌ 1 1 ┐ [ 1 1 ] * └ 1 0 ┘ = [ 2 1 ]

此外矩阵乘法具有结合律：A*B*.....*B=A*(B)ⁿ。

}

因此考虑：F(n) = F(n - 1) + F(n - 2)，我们可以将其递推式写为矩阵乘法：

                      ┌ 1 1 ┐ [ Fn-1 Fn-2 ] * └ 1 0 ┘ = [ Fn Fn-1 ]

也就是说，将初始的 $\begin{bmatrix} F1 &F0 \end{bmatrix}$ 乘以有系数矩阵 $\begin{bmatrix} 1& 1\\ 1& 0 \end{bmatrix}$ ，就可以递推得到 $\begin{bmatrix} F2 &F1 \end{bmatrix}$ 。

由于矩阵乘法具有结合律：A*B*.....*B=A*(B)ⁿ，我们可以先计算pow( $\begin{bmatrix} 1& 1\\ 1& 0 \end{bmatrix}$ ,n-1)，在执行 $\begin{bmatrix} F1 &F0 \end{bmatrix}$ *pow( $\begin{bmatrix} 1& 1\\ 1& 0 \end{bmatrix}$ ,n-1)，就可以得到 $\begin{bmatrix} Fn &Fn-1 \end{bmatrix}$ 。

算法过程

pow函数可以使用quick_pow快速实现。

我们还需要重载*运算符来实现矩阵乘法。

使用三重for循环枚举A的i行，B的j列以及A[i][k]*B[k][j] 。

using row = vector<long long>;
using matrix = vector<row>;
matrix operator *(const matrix& A, const matrix& B) {matrix ans(A.size(), row(B[0].size()));for (int i = 0; i < A.size(); i++)for (int j = 0; j < B[0].size(); j++)for (int k = 0; k < A[0].size(); k++)ans[i][j] = (ans[i][j] + A[i][k] * B[k][j]);return ans;
}

正如普通的quick_pow初始化ans为1，我们将矩阵快速幂的ans初始化为 $\begin{bmatrix} 1&0 \\ 0&1 \end{bmatrix}$ ，即单位矩阵，它的定位等同于1，任何矩阵乘以单位矩阵都等于原矩阵。

matrix quick_pow(matrix x, int n) {matrix ans={{1,0},{0,1}};while (n) {if (n & 1)ans = ans * x;x = x * x;n >>= 1;}return ans;
}

复杂度

时间复杂度: O(logn)

空间复杂度: O(1)

Code

long long quick_pow(long long x, int n) {long long ans = 1;while (n) {if (n & 1)ans *= x;x *= x;n >>= 1;}return ans;
}
using row = vector<long long>;
using matrix = vector<row>;
matrix operator *(const matrix& A, const matrix& B) {matrix ans(A.size(), row(B[0].size()));for (int i = 0; i < A.size(); i++)for (int j = 0; j < B[0].size(); j++)for (int k = 0; k < A[0].size(); k++)ans[i][j] = (ans[i][j] + A[i][k] * B[k][j]);return ans;
}
matrix quick_pow(matrix x, int n) {matrix ans={{1,0},{0,1}};while (n) {if (n & 1)ans = ans * x;x = x * x;n >>= 1;}return ans;
}
class Solution {
public:int fib(int n) {if (!n)return 0;matrix m = { {1,0} }, coefficient = { {1,1},{1,0} };matrix c = quick_pow(coefficient, n - 1);matrix ans = m * c;return ans[0][0];}
};

查看全文

http://www.mrgr.cn/news/53932.html