精益求精——斐波那契数列的logn解法

14天阅读挑战赛
努力是为了不平庸~

缘起：兔子数列

斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89...
这个数列从第3项开始，每一项都等于前两项之和。它因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。
斐波那契数列递推公式：

斐波那契数列很强，在现代物理、准晶体结构、化学等领域，斐波那契数列都有直接的应用。

通常求解斐波那契数列的算法有递归算法和动态规划算法，递归算法直接利用斐波那契数列的递推公式求解，递归调用递推公式，使时间复杂度为指数阶，当数列元素很多时，求解过程将是一场灾难。再来看动态规划，它会动态存储运算过程中的结果，使时间复杂度降到了多项式阶，较递归算法好了很多，那有没有更好的算法呢，我们知道，多项式阶时间复杂度好于指数阶时间复杂度，而对数阶时间复杂度比多项式阶时间复杂度更为优越，那有没有对数阶时间复杂度的算法可以求解斐波那契数列呢？答案是：有，必须的，嘿嘿。

计算一个数的幂

在讲解斐波那契数列求解之前，我们先来看看怎么更好的求解一个数的连乘，即一个数的幂次。比如求一个数的n次幂，最简单的做法是先求前两个数的乘积，得到的结果再去乘以第三个数，得到乘积再去乘以第四个数，不断重复，一直到n个数都乘完。这看上去很自然，那它的时间复杂度是多少呢？很明显，是O(n)，即多形式阶。

除了上面的方法，我们可以利用分治的思想，让n个数先两两相乘，得到的结果再两两相乘，可用递归算法求解，求解过程如下图所示

看，是不是二叉树的感觉出来了，很明显，有了类似树的结构，运算的时间复杂度就是O(logn)
具体计算公式如下

我们将数推广到矩阵，比如2x2阶矩阵，有类似的结论，只不过数的相乘就一次乘法运算，而两个2x2阶矩阵的相乘需要12次算术运算（相乘后的矩阵中，每个元素都需要两次乘法和一次加法获得），是两个数相乘所需运算量的12倍，但利用上面分治的思想，矩阵连乘运算的时间复杂度仍然是对数阶的。

数学归纳法

令P(n)是关于整数n的某个命题，假定我们需要证明P(n)对于所有正整数n为真，一种重要做法是:
(a) 证明P(1)为真;
(b) 证明“如果P(1)，P(2)....P(n-1)全部为真，那么P(n)也为真”，这个证明应对任意正整数n成立.
这就是著名的数学归纳法。

斐波那契数列的恒等式

斐波那契数列满足许多有趣的恒等式，其中一个恒等式可以用矩阵来表示为

我们可以用数学归纳法证明这个公式：
当n=1，F0=0，F1=1，F2=2，等式成立。
现在假设n-1项斐波那契数列满足恒等式，即

证明n项斐波那契数列也满足恒等式，根据矩阵乘法的定义，我们可以得到

这个恒等式有什么用呢，结合上一小节的结论我们不难发现，通过这个恒等式，我们就将斐波那契数列的求解变成了一个特殊矩阵的连乘，这样会使时间复杂度变成对数阶！！哈哈，我们找到了可以求解斐波那契数列并且时间复杂度是对数阶的算法！！

代码

import numpy as np

# 特殊矩阵
A = np.array([[1, 1], [1, 0]])

def fibonacci(n):
    if n <= 1:
        return A
    # 根据恒等式求解特殊矩阵连乘
    multi = np.dot(fibonacci(n>>1), fibonacci(n>>1))
    return multi if n & 1 == 0 else np.dot(multi, A)

# 算法主体
def run():
    # 数列元素个数
    N = 11
    # 求解斐波那契数列
    result = fibonacci(N-1)
    print("斐波那契数列第{}项是：{}".format(N, result[0][0]))

if __name__ == "__main__":
    run()

程序运行结果如下

斐波那契数列第11项是：89

作者这水平有限，有不足之处欢迎留言指正