求解斐波拉契数列的几种算法

    斐波纳契数列（Fibonacci Sequence），在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。

     求解Fibonacci第N项的值有几种方法，本文详细写出几种算法的实现，并验证算法的执行时间。

1、递归法 

     这是一种最直接的方法，从他的定义中可以直接得出，代码也很简单，如下：

   

//普通的递归算法 T(n) = T(n-1) + T(n-2)
	//指数级的时间复杂度
	public static long fiWithRecursion(int n){
		if ( n == 0) 
			return 0;
		else if ( n == 1)
			return 1;
		else 
			return fiWithRecursion(n - 1) + fiWithRecursion(n - 2);
	}

  从递归式，我们可以简单的猜到，求解T(N），需要先求解T(N-1)和T(N-2)，算法复杂度是指数级的，原因就是计算T(N）的时候，没有很好利用中间的计算结果，导致重复计算。

 

2、迭代法

   迭代法通过2个中间变量，循环迭代N次，算法复杂度为线性的。

//采用迭代算法
	//线性时间复杂度O(n)
	public static long fiWithIterator(int n){
		if ( n == 0)
			return 0;
		if ( n == 1)
			return 1;
		long f0 = 0;
		long f1 = 1;
		for(int i = 2; i<= n ; i++){
			long temp = f0;
			f0 = f1;
			f1 = temp + f1;
		}
		return f1;
	}

 

3、分治法

    分治法利用矩阵的乘法来实现，使时间复杂度降到O(lgN)，思想来源于神书《算法导论》，的确佩服算法的设计者，不说直接上全部代码。

 

 package com.xx.dataStructure;


   public class Fi {
	
	final static int [][] BASEMATRIX = {{1,1},{1,0} };
	
	//普通的递归算法 T(n) = T(n-1) + T(n-2)
	//指数级的时间复杂度
	public static long fiWithRecursion(int n){
		if ( n == 0) 
			return 0;
		else if ( n == 1)
			return 1;
		else 
			return fiWithRecursion(n - 1) + fiWithRecursion(n - 2);
	}
	
	//采用迭代算法
	//线性时间复杂度O(n)
	public static long fiWithIterator(int n){
		if ( n == 0)
			return 0;
		if ( n == 1)
			return 1;
		long f0 = 0;
		long f1 = 1;
		for(int i = 2; i<= n ; i++){
			long temp = f0;
			f0 = f1;
			f1 = temp + f1;
		}
		return f1;
	}
	
	//采用分治法的矩阵运算
	//对数的时间复杂度O(lgN)
	public static long fiWithMatrix(int n){
		if ( n == 0)
			return 0;
		if ( n == 1)
			return 1;
		int [][] data = recruit(n);
		return data[0][1];
	}
	
	private static int [][] recruit(int n){
		if (n == 1) 
			return BASEMATRIX;
		else if (n % 2 == 0){
			int [][] data = recruit(n/2);
			return matrixTimes(data,data,2);
		}else {
			int [][] data = recruit((n-1)/2);
			return matrixTimes(matrixTimes(data,data,2),BASEMATRIX,2);
		}
	}
	
	//分治法计算x^n
	public static int mm(int n,int x){
		if ( n == 0) 
			return 1;
		if ( n == 1)
			return x;
		else if ( n % 2 == 0){
			return mm(n/2,x) * mm(n/2,x);
		}
		else {
			return mm((n-1)/2,x) * mm((n-1)/2,x) * x ;
		}
	}
	
        //计算矩阵乘法
	private static int [][] matrixTimes(int [][] a, int [][] b,int n){
		int [][] c = new int[n][n];
		for(int i =0; i< n ; i++){
			for(int j =0; j< n ; j++){
				for(int k = 0; k< n ; k++){
					c[i][j] += a[i][k] * b[k][j];
				}
			}
		}
		return c;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		//0,1,1,2,3,5,8,13,21,34,55
		Long begin2 = System.nanoTime();
		fiWithRecution(15);
		Long end2 = System.nanoTime();
		System.out.println("user recure argrithom:   【" + (end2 - begin2) + "ns】");
		
		Long begin1 = System.nanoTime();
		fiWithIterator(1500000);
		Long end1 = System.nanoTime();
		System.out.println("user iterator argrithom: 【" + (end1 - begin1) + "ns】");
		
		Long begin3 = System.nanoTime();
		fiWithMatrix(1500000);
		Long end3 = System.nanoTime();
		System.out.println("user matrix argrithom:   【" + (end3 - begin3) + "ns】");
		
	}

}

 

程序执行结果如下：

 

user recure argrithom:   【161931ns】

user iterator argrithom:  【3665696ns】

user matrix argrithom:    【79255ns】

 

可见采用递归法求解N=15时消耗的时间就已经超过使用矩阵乘法分治求解N=1500000时时间消耗。

 

算法真是程序的灵魂。