斐波那契數(shù)列
由于斐波那契數(shù)列是以兔子的繁殖引入的，因此也叫“兔子數(shù)列”，它指的是這樣一個數(shù)列：0,1,1,2,3,5,8账胧，13...從這組數(shù)列可以明顯看出這樣一個規(guī)律：從第三個數(shù)開始窝剖，后邊一個數(shù)一定是在其之前兩個數(shù)的和，在數(shù)學(xué)上母廷，斐波那契數(shù)列可以以這樣的公式表示：
F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2),(n>=2)
實現(xiàn)方式1：遞歸
既然該數(shù)列已經(jīng)有這樣一個規(guī)律：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);
}
這樣的遞歸算法雖然只有簡單的幾行糊肤，但是效率卻很低琴昆，其時間復(fù)雜度為 O(n^2)
實現(xiàn)方式2：非遞歸
如果在時間復(fù)雜度和空間復(fù)雜度都有要求的話，我們可以使用非遞歸的算法來實現(xiàn)
- 1.時間復(fù)雜度為O(N)馆揉，空間復(fù)雜度為O(N)
創(chuàng)建一個數(shù)組业舍，每次將前兩個數(shù)相加后直接賦值給后一個數(shù)，這樣的話升酣，有N個數(shù)就創(chuàng)建包含N個數(shù)的一維數(shù)組舷暮，所以空間復(fù)雜度為O(N),由于只需從頭到尾遍歷一遍，時間復(fù)雜度為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,時間復(fù)雜度為O(N)噩茄，空間復(fù)雜度為O(1)
借助兩個遍歷first和second下面，每次將first和second相加后賦值給third，再將second賦值給first巢墅，third賦給second诸狭，如此循環(huán)
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;
}
公式法
實際上券膀，求斐波那契數(shù)列值有一個公式：
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);
}
其時間復(fù)雜度和空間復(fù)雜度就取決于JDK中這些數(shù)學(xué)公式的實現(xiàn)了，執(zhí)行效率也是非常高的
矩陣快速冪法
給個鏈接：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);
}
}
也是通過兩個變量保存計算值，傳遞給下一次進(jìn)行計算，遞歸的過程中也是根據(jù)n值變化逐步重復(fù)運算玻熙，和循環(huán)差不多，時間復(fù)雜度和空間復(fù)雜度也都一樣舒帮。
參考鏈接：
