斐波那契数列

2020-04-07 1599 words 4 minutes views

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

下面让我们用算法来实现它。

从上面可以看到，公式已经总结出来了：

F(1)=1、F(2)=1
F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

一、暴力递归

1
2
3
4
5
6


    public static int fib1(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

这个是最简单的办法，也很好理解，但是非常低效，以 n = 50 为例，

想要得到f(50),就得需要知道f(49)和f(48)的值，以此类推，f(49)需要f(48)和f(47)的值，直到分解到f(1) 或者 f(2)时，才会停止分解。

那我们看一下时间复杂度

递归算法的时间复杂度怎么计算？子问题个数乘以解决一个子问题需要的时间。

子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法操作，时间为 O(1)。

所以，这个算法的时间复杂度为 O(2^n)，指数级别，爆炸。

之所以这么慢，是因为存在大量的重复计算，而重算一遍就会浪费很多时间，所以我们需要优化一下。

二、备忘录方法（加缓存）

上面我们已经意识到是因为重复计算导致的效率问题，那么就对症下药，把已经算出来的结果保存起来，通常称之为备忘录方法，但我更愿意称它为加缓存方法。

这很好理解，在写业务时，查mysql的一个常量表，这些数据通常短时间不会改变，没必要每次都去直接查数据库，可以把结果缓存在redis中，如果命中缓存就无须查数据库了，在这里是同样的道理。

当然在这我们无需redis，只需要一个数组或者Hashmap就足够了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


    public static int fib(int n) {
        HashMap<Integer, Integer> map = new HashMap<>();
        return remember(map, n);
    }
    
    public static int remember(HashMap<Integer, Integer> map, int n) {
        int result = 1;
        if (n == 1 || n == 2) {
            return result;
        }
        if (!StringUtil.isEmpty(map.get(n))) {
            return map.get(n);
        } else {
            result = fib(n - 1) + fib(n - 2);
            map.put(n, result);
        }
        return result;
    }    

递归算法的时间复杂度怎么算？子问题个数乘以解决一个子问题需要的时间。

子问题个数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(50)，数量和输入规模 n = 50 成正比，所以子问题个数为 O(n)。
解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。

所以，本算法的时间复杂度是 O(n)。比起暴力算法，是降维打击。

上述的方法都是自顶而下的，先从f(50)开始，从上到下分解，直到f(1)、f(2)，那么反过来呢，自下而上呢？

三、动态规划（dynamic programming）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


    //返回值
    public static int fib3(int n) {
    	  //创建一个数组
        int[] dp = new int[n + 1];
        //[1,1]
        dp[0] = dp[1] = 1;
        //n = 3 ,则[1,1,2,3]
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n - 1];
    }

	  //返回数组	
    public static int[] fib4(int n) {
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp;
    }

这其实也是一种缓存的方式，和备忘录本质上没有区别，效率上也差不多。

但其实还是可以继续优化的

我们可以看出来，f(50) = f(49) + f(48),所以没必要把f(3)~f(47)都缓存起来，这样可以把复杂度降低到O(1)：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


    public static int fib2(int n) {
        if (n == 1 || n == 2)
            return 1;
        int prev = 1, curr = 1;
        for (int i = 3; i <= n; i++) {
            int sum = prev + curr;
            prev = curr;
            curr = sum;
        }
        return curr;
    }

算法没有那么神秘，它的出现是为了解决实际问题，如果我们把它神话，自己去敬畏它，又怎么能去大胆的使用它呢？

毕竟它们只是一堆晶体管啊😄（由衷佩服计算机史上的各位先贤）