在 O(logn) 时间和 space 复杂度中找到第 N 个斐波那契数？

Question

我想在 O(logn) 时间内找到第 N 个斐波那契数。我们可以使用 Fibonacci Q 矩阵进行 O(logn) 求解。

但是，还有一个 solution by using the Cassini and Catalan identities 可以在 O(logn) 时间内找到第 N 个斐波那契数列。它声明如下：

If n is even then k = n/2: F(n) = [2*F(k-1) + F(k)]*F(k)

If n is odd then k = (n + 1)/2: F(n) = F(k)*F(k) + F(k-1)*F(k-1)

我只能理解到标记方程的证明：

但是，我不理解下面的方程式和最终导出的方程式。

谁能详细解释一下？提前致谢。

Answer 1

我相信这个想法是采用这个矩阵乘积

 |1 1|^n   |1 1|^m    |1 1|^{m+n}
 |1 0|   x |1 0|    = |1 0|

并利用可以将其重写为

的事实

 |F_{n+1}    F_n    |   |F_{m+1}    F_m    |   |F_{m+n+1}    F_{m+n}  |
 |                  | x |                  | = |                      |
 |F_n        F_{n-1}|   |F_m        F_{m-1}|   |F_{m+n}      F_{m+n-1}|

现在，使用标准矩阵乘积公式将左边的矩阵相乘。你得到这个结果：

|F_{n+1} F_{m+1} + F_n F_m    F_{n+1}F_m + F_n F_{m-1}  |   |F_{m+n+1}    F_{m+n}  |
|                                                       | = |                      |
|F_n F_{m+1} + F_{n-1} F_m    F_n F_m + F_{n-1} F_{m-1} |   |F_{m+n}      F_{m+n-1}|

这给出了这四个等式：

F_n+1F_m+1 + F_nF_m = F_m+n+1
F_n+1F_m + F_nF_m-1 = F_m+n
F_nF_m+1 + F_n-1F_m = F_m+n
F_nF_m + F_n-1F_m-1 = F_m+n-1

剩下的等式通过代入特定的 m 和 n 值而消失。

在 O(logn) 时间和 space 复杂度中找到第 N 个斐波那契数？

Finding Nth Fibonacci Number in O(logn) time and space complexity?

algorithm

math

matrix

fibonacci