本系列導航：劍指offer（第二版）java實現(xiàn)導航帖
面試題10：斐波那契數(shù)列
題目要求：
求斐波那契數(shù)列的第n項的值梧兼。f(0)=0, f(1)=1, f(n)=f(n-1)+f(n-2) n>1
解法比較：
解法3,4將問題數(shù)學化我碟，借助數(shù)學工具的推導饵较，從根本上減低時間復雜度。
| 解法 | 解法介紹 | 時間復雜度 | 空間復雜度 |
|---|---|---|---|
| 解法1 | 依定義遞歸求解 | o(n^2) | o(1) |
| 解法2 | 從0開始迭代求解 | o(n) | o(1) |
| 解法3 | 借助等比數(shù)列公式 | o(logn) | o(1) |
| 解法4 | 借助通項公式 | o(1) | o(1) |
代碼：
package chapter2;
/**
* Created by ryder on 2017/6/21.
* 斐波那契數(shù)列
* f(0)=0,f(1)=1,f(n)=f(n-1)+f(n-2) n>1
*/
public class P74_Fibonacci {
// 依據(jù)原始概念的遞歸解法筒占，時間復雜度o(n^2)
public static int fibonacci1(int n){
if(n<=0)
return 0;
if(n==1)
return 1;
return fibonacci1(n-1)+fibonacci1(n-2);
}
// 當前狀態(tài)只與前兩個狀態(tài)有關(guān)卓缰。存儲前兩個值牡昆，計算后一個，迭代進行掂器。時間復雜度o(n)
public static int fibonacci2(int n){
if(n<=0)
return 0;
if(n==1)
return 1;
int temp1 =0,temp2=1;
int result = temp1 + temp2,i=3;
while(i<=n){
//也可用一個隊列來完成下面三行的操作
temp1 = temp2;
temp2 = result;
result = temp1+temp2;
i++;
}
return result;
}
// 借助如下數(shù)學公式解決問題亚皂。矩陣乘法部分，可用遞歸解決国瓮，時間復雜度o(logn)
// [ f(n) f(n-1) ] = [ 1 1 ] ^ n-1 (當n>2)
// [f(n-1) f(n-2) ] [ 1 0 ]
// 證明:
// [ f(n) f(n-1) ] = [ f(n-1)+f(n-2) f(n-1)] = [ f(n-1) f(n-2)] * [1 1]
// [f(n-1) f(n-2) ] [ f(n-2)+f(n-3) f(n-2)] [ f(n-2) f(n-3)] [1 0]
// 得到如上遞推式灭必，所以
// [ f(n) f(n-1) ] = [ f(2) f(1)] * [1 1]^n-2 = [1 1]^n-1
// [f(n-1) f(n-2) ] [ f(1) f(0)] [1 0] [1 0]
public static int fibonacci3(int n){
int[][] start = {{1,1},{1,0}};
return matrixPow(start,n-1)[0][0];
}
public static int[][] matrixPow(int[][] start,int n){
if((n&1)==0){
int[][] temp = matrixPow(start,n>>1);
return matrixMultiply(temp,temp);
}
else if(n==1){
return start;
}
else{
return matrixMultiply(start,matrixPow(start,n-1));
}
}
public static int[][] matrixMultiply(int[][] x,int[][] y){
int[][] result = new int[x.length][y[0].length];
for(int i=0;i<x.length;i++){
for(int j=0;j<y[0].length;j++){
int sum = 0;
for(int k=0;k<x[0].length;k++){
sum += x[i][k]*y[k][j];
}
result[i][j] = sum;
}
}
return result;
}
// 使用通項公式完成，時間復雜度o(1)
// f(n) = (1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
// 推導過程可參考https://wenku.baidu.com/view/57333fe36bd97f192379e936.html
public static int fibonacci4(int n){
double gen5 = Math.sqrt(5);
return (int)((1/gen5)*(Math.pow((1+gen5)/2,n)- Math.pow((1-gen5)/2,n)));
}
public static void main(String[] args){
System.out.println(fibonacci1(13));
System.out.println(fibonacci2(13));
System.out.println(fibonacci3(13));
System.out.println(fibonacci4(13));
}
}
運行結(jié)果
233
233
233
233
