斐波那契数列求解的三种方法

题目：求菲波那切数列的第n项

1.递归：剑指offer代码

 2.DP/循环实现：剑指offer代码：O（n）

 3.特殊公式但不太实用O（logn）：剑指offer代码

公式：

所以求得矩阵的n-1次即可得到f（n） Ps：对应项相等

如果简单的从0到n来循环计算乘方复杂度还是O（n）

所以用此性质：

 可见复杂度为O（logn）

相关题：