《面试题甄选》15.O(logn)求Fibonacci数列

《面试题精选》15.O(logn)求Fibonacci数列
题目：定义Fibonacci数列如下：

        /    0                      n=0
f(n)=      1                      n=1
        \    f(n-1)+f(n-2)          n=2

输入n，用最快的方法求该数列的第n项。

分析：刚看到这道题的时候，还以为怎么会有这么简单，汗，原来理所当然的使用的递归，时间复杂度太大，看看下面这段递归代码。

public static int fun(int n){
	if(n==0) return 0 ;
	else if(n==1) return 1 ;
	else return (fun(n-1)+fun(n-2)) ;
}

大家来分析下，比如要求f(10)，那么他的 运算过程如下图：

 f(10)
               /        \
            f(9)         f(8)
          /     \       /    \
       f(8)     f(7)  f(7)   f(6)
      /   \     /   \ 
   f(7)  f(6)  f(6) f(5)

从上面的树状结构中就可以知道利用递归的方法会有许多重复的节点，而且n越大重复节点越多。他的时间复杂度是以n的指数的方式递增的。

那么要做的优化，第一个想到的就是去除重复，如何去除呢？我们可以从f(0),f(1)开始运算，利用循环来按顺序求出f(n)。这样的时间复杂度是O(n),代码如下

public static int fun1(int n){
	int fib1 = 0 ;
	int fib2 = 1 ;
	int fibsum = 0 ;
	if(n<0) System.out.println("error") ;
	else if(n==0) return 0 ;
	else if(n==1) return 1 ;
	else{
		for(int i=1;i<n;i++){
			fibsum = fib1 + fib2 ;
			fib1 = fib2 ;
			fib2 = fibsum ;
		}
	}
	return fibsum ;
}

总结：慎重使用递归。