[优化] 十行代码完成斐波数列算法优化

概述

废话不多数，先上代码。

斐波那契数列（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年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

@Slf4j
public class FiboBefore {
    public static void main(String[] args) {
        System.out.println(fibo(7));
    }

    public static int fibo(int n){
        if (n<3) return 1;
        int fiboN = fibo(n-1) + fibo(n-2);
        log.info("计算第{}个斐波数列{}", n, fiboN);
        return  fiboN;
    }
}

// 控制台输出日志如下
2019-02-28 10:51:28,387 INFO 585 [main] [cn.lee.test.FiboBefore:19]: 计算第3个斐波数列2
2019-02-28 10:51:28,397 INFO 595 [main] [cn.lee.test.FiboBefore:19]: 计算第4个斐波数列3
2019-02-28 10:51:28,397 INFO 595 [main] [cn.lee.test.FiboBefore:19]: 计算第3个斐波数列2
2019-02-28 10:51:28,398 INFO 596 [main] [cn.lee.test.FiboBefore:19]: 计算第5个斐波数列5
2019-02-28 10:51:28,398 INFO 596 [main] [cn.lee.test.FiboBefore:19]: 计算第3个斐波数列2
2019-02-28 10:51:28,398 INFO 596 [main] [cn.lee.test.FiboBefore:19]: 计算第4个斐波数列3
2019-02-28 10:51:28,398 INFO 596 [main] [cn.lee.test.FiboBefore:19]: 计算第6个斐波数列8
2019-02-28 10:51:28,398 INFO 596 [main] [cn.lee.test.FiboBefore:19]: 计算第3个斐波数列2
2019-02-28 10:51:28,399 INFO 597 [main] [cn.lee.test.FiboBefore:19]: 计算第4个斐波数列3
2019-02-28 10:51:28,399 INFO 597 [main] [cn.lee.test.FiboBefore:19]: 计算第3个斐波数列2
2019-02-28 10:51:28,399 INFO 597 [main] [cn.lee.test.FiboBefore:19]: 计算第5个斐波数列5
2019-02-28 10:51:28,402 INFO 600 [main] [cn.lee.test.FiboBefore:19]: 计算第7个斐波数列13
13

分析

如果我们想要用程序实现计算第N个斐波数列的值？

一般思路是编写递归，F(n)=F(n-1)+F(n-2)，也就是说，第N个斐波数列的值，等于前两个斐波数列值之和。

想到这，肯定是要用递归调用。比如为了计算第5个斐波数列的值，需要计算第4个（步骤1）和第3个（步骤2）斐波数列值。

计算步骤1也就是计算第4个斐波数列值，需要计算第3个斐波数列值和第2个斐波数列值。

计算步骤2也就是计算第3个斐波数列值，需要计算第2个斐波数列值和第1个斐波数列值。

那么步骤1和步骤2中，相当于重复计算了两次第3个斐波数列和两次第2个斐波数列值。

想想一下，假如我们计算的是第N个斐波数列值，n越小，计算的重复次数越多，而且是指数级增长。

上面的日志中已经验证了，简单递归的弊端。

 

优化

整体优化思路：

其实比如步骤1中，既然已经计算出了第3个斐波数列了，假如我们把每次计算过的值，都缓存起来，那步骤2中再次计算第3个斐波数列值时，就可以直接拿过来用了。

可见改良后，我们对于计算第N个斐波数列值，仅需要计算N次。

改良后的代码：

@Slf4j
public class Fibo {
    public static void main(String[] args) {
        int n = 13;
        int[] temp = new int[n];
        System.out.println(fibo(n, temp));
    }

    public static int fibo(int n, int[] temp){
        if (n<3) return 1;
        int before = temp[n - 2] == 0 ? fibo(n-1, temp) : temp[n - 2]; // 优先从缓存数组中寻找n-1斐波数列值
        int beforeTow = temp[n - 3] == 0 ? fibo(n-2, temp) : temp[n - 3];// 优先从缓存数组中寻找n-2斐波数列值
        temp[n - 1] = before + beforeTow;  //将计算得到的第n个斐波数列缓存到数组
        log.info("计算第{}个斐波数列值{}", n, temp[n-1]);
        return  temp[n-1];
    }
}

// 控制台日志输出，仅仅输出13 - 2次
2019-02-28 10:56:00,452  INFO [main][cn.lee.Fibo:23] : [0] 计算第3个斐波数列2
2019-02-28 10:56:00,465  INFO [main][cn.lee.Fibo:23] : [0] 计算第4个斐波数列3
2019-02-28 10:56:00,465  INFO [main][cn.lee.Fibo:23] : [0] 计算第5个斐波数列5
2019-02-28 10:56:00,466  INFO [main][cn.lee.Fibo:23] : [0] 计算第6个斐波数列8
2019-02-28 10:56:00,466  INFO [main][cn.lee.Fibo:23] : [0] 计算第7个斐波数列13
2019-02-28 10:56:00,466  INFO [main][cn.lee.Fibo:23] : [0] 计算第8个斐波数列21
2019-02-28 10:56:00,467  INFO [main][cn.lee.Fibo:23] : [0] 计算第9个斐波数列34
2019-02-28 10:56:00,467  INFO [main][cn.lee.Fibo:23] : [0] 计算第10个斐波数列55
2019-02-28 10:56:00,467  INFO [main][cn.lee.Fibo:23] : [0] 计算第11个斐波数列89
2019-02-28 10:56:00,467  INFO [main][cn.lee.Fibo:23] : [0] 计算第12个斐波数列144
2019-02-28 10:56:00,469  INFO [main][cn.lee.Fibo:23] : [0] 计算第13个斐波数列233
233