斐波那契数列算法

1、概述

斐波那契数列可以说我们从中学就已经接触了这种数列，具体的应用问题不在这里列出来啦，这个数列是长成这样子的：

0、1、1、2、3、5、8、13…

也就是说，后一项是前两项的和，对应的函数表达式可以为：F(n) = F(n-1) + F(n-2)，n >1;

下面带来这种算法的几种常见的解题：

2、算法

2.1 递归法

当一个算法可以用一个递归的函数来表达式，我们就可以直接使用编程中的递归思想来解决这种问题。直接上代码

    public static int method_one(int n){
        return n < 2 ? n : method_one(n - 1) + method_one(n - 2);
    }

这个递归算法比较简单，熟练使用三目运算符的话，一行代码就解决了。

时间复杂度：O(2^N)

空间复杂度: O(2N) = O(N)（递归带来的java栈的内存开销）

2.2 自底向上的方法

知道了要计算的那个数的位置，此时直接按照规律累加该位置前面的数列和

    public static int method_two(int n){
        return n < 2 ? n :cash(n);
    }
    public static int cash(int n){
        int[] cash = new int[n + 1];
        cash[0] = 0;
        cash[1] = 1;
        for (int i = 2; i < cash.length; i++) {
            cash[i] = cash[i-1] + cash[i-2];
        }
        return cash[n];
    }

时间复杂度：O(N)

空间复杂度：O(N)（创建数组带来的内存开销）

2.3 自顶向下的方法

这个算法我也是在leetcode上看到的，当时看到的时候以为就是一个普通的递归算法，和第一种没有什么太大的区别。但是仔细看了一遍之后感觉绕不出来。。。应该还是递归这方面的逻辑能力还不够强。这里详细的说一下。

	public static Integer[] cache = new Integer[31];

    public static int method_three(int n){
        if (n < 2){
            return n;
        }
        cache[0] = 0;
        cache[1] = 1;
        return memorize(n);
    }

    public static int memorize(int n){
        if (cache[n] != null) {
            return cache[n];
        }
        // 这里使用了两个递归
        cache[n] = memorize(n-1) + memorize(n-2);
        // 但是仔细观察可以发现，当上面的步骤完成的时候，下面的递归调用实际上返回的是cashe[n]
        // 所以下面的代码等价于
        // return cashe[n];
        return memorize(n);
    }

时间复杂度：O(N)

空间复杂度：O(N)(创建数组带来的内存开销)

我一开始看到这个算法的时候，第一印象就是那么多递归使用，时间复杂度和空间复杂度怎么只有O(N)？于是自己通过调试发现原来并没有那么简单，感觉不是自己所了解的那种递归算法的，这种情况下，最能帮助自己理解的方法就是画图。于是乎，我打开了processOn:

我们假设输入的数字是5，这个数的理想输出结果是5。按照上面的程序，从method_three方法中的return memorize开始，运行流程如下：

2.4 自底向上进行迭代

这个算法实际上和我们自己手动计算差不多，就是通过前面的一个一个的数去慢慢地累加，知道累加到需要求得的位置上的数。是最好理解的。

    public static int method_four(int n){
        if (n < 2)
            return n;
        int pre1 = 0;
        int pre2 = 1;
        int current = 0;
        for (int i = 1; i < n; i++) {	// 注意这里循环的次数要与n的位置对应
            current = pre1 + pre2;
            pre1 = pre2;
            pre2 = current;
        }
        return current;
    }

3、总结

想起一开始接触斐波那契数列的时候，因为没有好好学，当从某些地方看到这个数列的时候，只记得那个时候有一种递归的方法写起来很是简洁的——这就是因为懒吧，什么时间、空间复杂度都没有考虑，单单考虑了怎么样写得代码量是最少的。其实那个时候，连简单的递归算法都不能很快地写出了，关键在于不能找准跳出递归的条件。