算法：斐波那契数列(java实现)

斐波那契数列

由于斐波那契数列是以兔子的繁殖引入的，因此也叫“兔子数列”，它指的是这样一个数列：0,1,1,2,3,5,8，13...从这组数列可以明显看出这样一个规律：从第三个数开始，后边一个数一定是在其之前两个数的和，在数学上，斐波那契数列可以以这样的公式表示：
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2),(n>=2)

实现方式1：递归

既然该数列已经有这样一个规律：F(n)=F(n-1)+F(n-2);那么我们可以用递归的方法，这样的代码比较简洁

 long fbnq1(long num) {
        if (num == 1 || num == 0) {
            return num;
        }
        return fbnq1(num - 1) + fbnq1(num - 2);
    }

    //也可以这样写
    long fbnq(long n) {
        return n < 2 ? n : fbnq(n - 1) + fbnq(n - 2);
    }

这样的递归算法虽然只有简单的几行，但是效率却很低，其时间复杂度为 O(n^2)

实现方式2：非递归

如果在时间复杂度和空间复杂度都有要求的话，我们可以使用非递归的算法来实现

• 1.时间复杂度为O(N)，空间复杂度为O(N)
  创建一个数组，每次将前两个数相加后直接赋值给后一个数，这样的话，有N个数就创建包含N个数的一维数组，所以空间复杂度为O(N),由于只需从头到尾遍历一遍，时间复杂度为O(N)

    long[] fbnq4Array(long n) {
        long[] array = new long[(int) (n + 1)];
        array[0] = 0;
        array[1] = 1;
        for (int i = 2; i <= n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array;
    }

• 2,时间复杂度为O(N)，空间复杂度为O(1)
  借助两个遍历first和second，每次将first和second相加后赋值给third，再将second赋值给first，third赋给second，如此循环

    long fbnq3(long n) {
        long first = 1;
        long second = 1;
        long third = 0;
        for (int i = 3; i <= n; i++) {
            third = first + second;
            first = second;
            second = third;
        }
        return third;
    }

参考链接：

• 使用Java打印斐波那契数列的三种方法
  
• Java实现斐波那契数高效算法