logN求Fibonacci数列第N项
- 斐波那契数列通项公式
F
(
i
)
=
F
(
i
−
1
)
+
F
(
i
−
2
)
F(i)=F(i-1)+F(i-2)
F(i)=F(i−1)+F(i−2)
- 以下介绍两种复杂度为
O
(
l
o
g
N
)
O(logN)
O(logN)的算法
- 两种方法思想类似
1. 动态规划
- 当我们尝试将
F
(
i
−
1
)
F(i-1)
F(i−1)和
F
(
i
−
2
)
F(i-2)
F(i−2)进行继续拆解时（始终保持两项），发现两项的系数始终是斐波那契数列中的某一相邻两项
- 因此，F(i)一定可以可以由4个项组成
-
F
(
i
)
=
F
(
i
−
a
)
F
(
i
−
x
)
+
F
(
i
−
b
)
F
(
i
−
(
x
−
1
)
)
F(i)=F(i-a)F(i-x)+F(i-b)F(i-(x-1))
F(i)=F(i−a)F(i−x)+F(i−b)F(i−(x−1))
- 当
a
=
0
a=0
a=0时则为
F
(
i
)
=
F
(
2
)
F
(
i
−
1
)
+
F
(
1
)
F
(
i
−
2
)
F(i)=F(2)F(i-1)+F(1)F(i-2)
F(i)=F(2)F(i−1)+F(1)F(i−2)
- 且a，b，x具有一定关系
思路
a，b，x有多种可能
此时需要算4个小项才能合并到1个大项
若这4个项中有相同的项，则可以简化计算
此外，越大的项，计算的复杂度越大，反之越小
因此我们可以想到取
i
/
2
i/2
i/2 附近的项
- 通过递推得（也可以用较小的
i
i
i找找规律）
- 当
i
i
i为奇数时，
F
(
i
)
=
F
2
(
i
/
2
+
1
)
+
F
2
(
i
/
2
)
F(i)=F^2(i/2+1)+F^2(i/2)
F(i)=F2(i/2+1)+F2(i/2)
- 当
i
i
i为偶数时，
F
(
i
)
=
F
(
i
/
2
+
1
)
∗
F
(
i
/
2
)
+
F
(
i
/
2
)
∗
F
(
i
/
2
−
1
)
F(i)=F(i/2+1)*F(i/2)+F(i/2)*F(i/2-1)
F(i)=F(i/2+1)∗F(i/2)+F(i/2)∗F(i/2−1)
即我们将一个递推项分成2或3项分别计算后再合并
- 可以分析复杂度为
O
(
l
o
g
N
)
O(logN)
O(logN)
-
注：在实际程序实现中，不能直接
return F(i/2+1)*F(i/2)+F(i/2)*F(i/2-1)，这样会造成计算冗余
- 应该先保存下结果，计算后
return
DP代码
int Fibonacci(int x) // logN
{
if (x == 1 || x == 2) return 1;
if (x % 2 != 0)
{
int F1 = Fibonacci(x / 2 + 1), F2 = Fibonacci(x / 2);
return F1 * F1 + F2 * F2;
}
else
{
int F1 = Fibonacci(x / 2 + 1), F2 = Fibonacci(x / 2), F3 = Fibonacci(x / 2 - 1);
return F1 * F2 + F2 * F3;
}
}
2. 矩阵分治
- 结合矩阵的知识，我们可以知道斐波那契数列符合
- 于是随着等号右边中的斐波那契项的项数
i
i
i降低，该矩阵就不断左乘
因此可以基于矩阵结合律计算若干项矩阵乘积，再左乘
F
(
1
)
a
n
d
F
(
2
)
F(1) and F(2)
F(1)andF(2)
- 设该矩阵
为A
- 则
A
n
=
A
n
/
2
∗
A
n
/
2
A^n=A^{n/2}*A^{n/2}
An=An/2∗An/2
- 其中
A
n
/
2
A^{n/2}
An/2只需计算一项
- 依次类推
这就是快速幂的思想
代码
int[2][2] Matrix(int x)
{
int a[2][2] = { { 1, 1 }, { 0, 1 } };
if (x == 1) return a;
int b[2][2] = Matrix(x / 2);
if (x % 2 == 0) return b * b; // 省略矩阵乘法
return b * b * a;
}
