问题描述

Fibonacci数（Fibonacci Number）的定义是：F(n) = F(n - 1) + F(n - 2)，并且F(0) = 0，F(1) = 1。对于任意指定的整数n（n ≥ 0），计算F(n)的精确值

递归法

一个看起来很直观、用起来很恐怖的算法就是递归法。根据Fibonacci的递推公式，对于输入的n，直接递归地调用相同的函数分别求出F(n - 1)和F(n - 2)，二者相加就是结果。递归的终止点就是递推方程的初值，即n取0或1的时候。

程序写出来那也是相当的简洁直观：

private static long recursiveFibonacci(int n) {
    if (n == 0)
        return 0;
    if (n == 1)
        return 1;
    
    return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
}

非递归算法 - 递推法

虽然只是一字之差，但递推法的复杂度要小的多。这个方法就是按照递推方程，从n = 0和n = 1开始，逐个求出所有小于n的Fibonacci数，最后就可以算出F(n)。由于每次计算值需要用到前两个Fibonacci数，更小的数就可以丢弃了，可以将空间复杂度降到最低。算法如下：

private static long fibonacci1(int n) {
    int result[] = {0, 1};
    if (n < 2)
        return result[n];

    long fibFrontPart = 1;
    long fibTailPart = 0;
    long fibN = 0;

    int i = 2;
    while (i <= n) {
        fibN = fibFrontPart + fibTailPart;

        fibTailPart = fibFrontPart;
        fibFrontPart = fibN;
        i++;
    }
    return fibN;
}

可以很明显的看到计算第n项的时间复杂度为 T(n) = O(n)

非递归算法 - 公式算法

对于斐波那契数列这个常见的递推数列，其第nn项的值的通项公式如下： $$ Fn=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n−(\frac{1−\sqrt{5}}{2})^n] $$ 该公式可以通过构造等比数列或者特征方程法等方法求出，也可以利用数学归纳法进行证明，在这里不多介绍。如果将公式转化成Python代码则有以下程序：

def Fibonacci_formula(n):
    root_five = 5**0.5
    result = (((1 + root_five) / 2)**n - ((1 - root_five) / 2)**n) / root_five
    return int(result)

该方法虽然看起来高效，但是由于涉及大量浮点运算，在nn增大时浮点误差不断增大会导致返回结果不正确甚至数据溢出。由于这种不可靠性，一般不采用这种方法进行计算。

矩阵算法

Reference

五种方法计算斐波那契数列的第n项- http://blog.zhengyi.one/fibonacci-in-logn.html

FEATURED TAGS

algorithm algorithmproblem architecturalpattern architecture aws c# cachesystem codis compile concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress xml zookeeper

【Algorithm】计算斐波纳契数（Fibonacci Number）