斐波那契数列O(logn)的求解方法

本文主要是介绍斐波那契数列O(logn)的求解方法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言

是的，没错，斐波那契数列除了递推、递归算法之外，还有更加高效的求解方法，那就是矩阵运算+快速幂。

思路：
可以先利用矩阵运算的性质将通项公式变成幂次形式，然后用平方倍增（快速幂）的方法求解第 n 项。

首先我们定义向量
X_n=[a_n a_n−1],边界：X₁=[a₁ a₀]
然后我们可以找出矩阵：
$$A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$$
则有：
X_n=X_n−1×A
所以&

这篇关于斐波那契数列O(logn)的求解方法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---