利用数组高速实现斐波那契数

利用数组快速实现斐波那契数

 

     斐波那契数一般都是采用递归来予以实现的，但是这存在一个严重的问题——即使在相对较快的计算机上，计算F40需要大约一分钟的时间，就运行时间而言，这是很荒谬的，因为基本运算只需要39次加法。

     根本问题是：递归历程执行了冗余计算，为了计算fib（n） ，我们递归的计算fib（n-1）。当递归使用另一个递归调用，我们计算fib（n-2）。不过，在计算fib（n-1）的过程中，我们早已计算了 fib（n-2），所以调用 fib（n-2） 是一种浪费，是冗余计算。对于N=40，F40=102334155，但是递归调用的总次数超过了300 000 000次！！！

    这里我采用数组实现斐波那契，速度相当的快，代码如下：相互运算时间的比较代码我就不具体贴出来了，很简单。有兴趣的可以用递归的方法与我的方法进行比较，结果一目了然。

 

/**
 * 使用数组利用循环快速实现斐波那契数
 * @author jw
 *
 */
public class Ftest {
   public static long fib(int n){
	  if(n<2){
		  System.out.println("必须输入大于2的数字");
		  return 0;
	  }		  
	 else{
		 int[] a=new int[n+1];	
		 a[0]=0;
		 a[1]=1;
		 for(int i=2;i<=n;i++){
			 a[i]=a[i-1]+a[i-2];
		 }
		 return a[n];
	 }	 
   }
   public static void main(String[] args){
	  System.out.println(fib(40)) ;
	  System.out.println(fib(1)) ;
	  System.out.println(fib(2)) ;
	  System.out.println(fib(10)) ;
	  System.out.println(fib(1000)) ;
   }
}