1.斐波那契数列

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

2.Java实现

2.1递归

时间复杂度和空间复杂度都为 n的平方

    //递归算法 时间复杂度 O(n2) 空间复杂度O(n2)
    public static int fab(int n){
        if (n <=2){
            return 1;
        }
        return fab(n-1)+fab(n-2);
    }

1
2
3
4
5
6
7
8

    public static void main(String[] args){
        for (int i =1 ; i <46 ;i++){
            long start = System.currentTimeMillis();
            System.out.println(i+"："+fab(i)+" 花费时间："+(System.currentTimeMillis()-start)+"ms");

        }

    }
1
2
3
4
5
6
7
8

打印结果：

可以看出来递归是越来越耗时的。

2.2非递归

非递归 ：时间复杂度 O(n) 空间复杂度O(n)

 
 public static int nofab(int n){
        if (n <=2){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = 0;
       for (int i=3;i<=n;i++){
            c = a +b;
            a = b;
            b = c;
       }

       return c;

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

   public static void main(String[] args){
        for (int i =1 ; i <46 ;i++){
            long start = System.currentTimeMillis();
            System.out.println(i+"："+nofab(i)+" 花费时间："+(System.currentTimeMillis()-start)+"ms");

        }

    }
1
2
3
4
5
6
7
8

2.3 用数组进行缓存

用数组进行缓存：将已经计算出来的值存在数组里避免了重复计算
时间复杂度 O(n) 空间复杂度O(n)

    private static int data[] ;
    public static int fab2(int n){
        if (n <=2){
            return 1;
        }

        if (data[n] >0){
            return data[n];
        }

        int res =fab2(n-1)+fab2(n-2);
        data[n] = res;

        return res;
    }

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

  public static void main(String[] args){
        data=new int[46];
        for (int i =1 ; i <46 ;i++){
            long start = System.currentTimeMillis();
            System.out.println(i+"："+fab2(i)+" 花费时间："+(System.currentTimeMillis()-start)+"ms");

        }

    }

1
2
3
4
5
6
7
8
9
10

打印结果：

3.总结

好记性不如烂笔头，知道不如做到。