2012年5月7日---基于斐波那契数列的时间复杂度分析

在算法中，时间复杂度是衡量一个算法好坏的重要标准。

递归调用在算法中可以非常直观有效的解决我们的问题，但是由于其调用的时候需要花大量的时间，所以我们一般都会刻意的避免使用递归去完成我们的算法。

在这里，我就用斐波那契数列的递归构造和非递归构造来分析递归和非递归的时间复杂度。

先看具体的代码极其运行的时间：

 

/*
 * 比较递归和非递归求斐波那契数的时间效率
 * @version 2012/5/7
 * @author akon
 */
package com.akon405.www;

public class Fibonacci {
	//递归求斐波那契数列
	public int rFibonacci(int n){
		int x=n;
		if(x<=1){
			return x;
		}
		x=rFibonacci(x-1)+rFibonacci(x-2);
		return x;
	}
	//非递归求斐波那契数列
	public int uRFibonacci(int n){
		int x=1;
		int y=1;
		int tmp;
		for(int i=2;i<n;i++){
			tmp=x;
			x=y;
			y=y+tmp;
		}
		return y;
	}
	public static void main(String[] args) {
		double d1,d2,d3;
		Fibonacci f=new Fibonacci();
		System.out.println("递归求斐波那契数列：");
		d1=System.currentTimeMillis();
		for(int i=1;i<=40;i++){
		System.out.println(f.rFibonacci(i));
		}
		d2=System.currentTimeMillis();
		d3=d2-d1;
		System.out.println("递归求斐波那契数列的时间:"+d3);
		System.out.println("非递归求斐波那契数列：");
		d1=System.currentTimeMillis();
		for(int i=1;i<=40;i++){
			System.out.println(f.uRFibonacci(i));
		}
		d2=System.currentTimeMillis();
		d3=d2-d1;
		System.out.println("非递归求斐波那契数列的时间:"+d3);
	}
}

运算结果：（只保留部分结果）

递归求斐波那契数列：
1
1
2
3
5
.
.
102334155
递归求斐波那契数列的时间:4322.0
非递归求斐波那契数列：
1
1
2
3
5
.
.
102334155
非递归求斐波那契数列的时间:3.0

 通过结果就可以大致看出，递归调用的时间是非递归调用的很多倍。并且这种情况在n越大的时候越明显。

 

在分析算法的时间复杂度的时候，我们也可以得到相同的结果，非递归使用的是for循环，其时间复杂度为O(n)。而递归的时间复杂度则比较复杂，其分析出来为O(2^n)。

这里需要说明的就是，非递归的for循环其时间复杂度O(n)虽然很小，但是其空间复杂度缺比递归调用差得多。因为，for循环在每次循环的时候，都把相应的数值保存下来了，而递归调用却不会保存相应的数值。