1. 效率很低的解法
public static long fibonacci1(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fibonacci1(n-1) + fibonacci1(n-2);
}
缺點：遞回求解的程序中，有很多的節點是重復的，而且重復的節點數會隨著n的增大而急劇增加，這就意味著計算量會隨著n的增大而急劇增大，
2. 避免重復節點的方法
從下往上計算，首先根據f(0)和f(1)算出f(2),f(1)和f(2)算出f(3)···以此類推就可以算出第n項了，時間復雜度是O(n)，
public static long fibonacci2(int n) {
if (n == 1 || n == 2) return 1;
long fibNMinusOne = 1; // 用來記錄計算項的前面的前面的數
long fibNMinusTwo = 1; // 用來記錄當前計算項的前一項
long fibN = 0; //用來記錄結果
for (int i = 2; i < n; i++) {
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}
3.時間復雜度為O(logn)但不夠實用的解法
public static int fibonacci3(int n) {
if (n == 0) return 1;
if (n == 1) return 1;
//n為偶數
if (n % 2 == 0) return fibonacci3(n / 2) * fibonacci3(n / 2) + fibonacci3(n / 2 - 1) * fibonacci3(n / 2 - 1);
//n為奇數
else return fibonacci3(n / 2) * fibonacci3(n / 2 + 1) + fibonacci3(n / 2 - 1) * fibonacci3(n / 2);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121709.html
標籤：其他