斐波那契数列
由于斐波那契数列是以兔子的繁殖引入的，因此也叫“兔子数列”，它指的是这样一个数列：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;
}
公式法
实际上，求斐波那契数列值有一个公式：
public int fbnq4(int n ){
double c =Math.sprt(5);
return (int) ((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
}
其时间复杂度和空间复杂度就取决于JDK中这些数学公式的实现了，执行效率也是非常高的
矩阵快速幂法
给个链接：https://blog.csdn.net/computer_user/article/details/86927209
尾递归法
public int fbnq5(int n,int first,int second){
if(n<=1){
return first;
}else{
return fbnq5(n-1,second,first+second);
}
}
也是通过两个变量保存计算值，传递给下一次进行计算，递归的过程中也是根据n值变化逐步重复运算，和循环差不多，时间复杂度和空间复杂度也都一样。
参考链接：
