首页 > 代码库 > Fibonacci 0,1,1,2,3,5,8…… 数列的实现

Fibonacci 0,1,1,2,3,5,8…… 数列的实现

Fibonacci 0,1,1,2,3,5,8…… 数列的实现
下面是对这个数列的两种算法实现,一种是递归实现,一种是多项式算法实现!在第一种情况下,当n值达到一定大小时,计算机的运行时间明显加大,对其的改进的第二种方法说是秒杀了第一种算法!
递归算法的时间复杂度是指数级别

多项式算法的时间复杂度是线性增长级别


package review;

public class Fibonacci {
	public static void main(String args[]){
		int n=200;
		//多项式发
		fib1(n);
		//递归法
		for(int i=0;i<=n;i++)
		{
			System.out.println(fib(i));
		}	
		
	}
	//递归法(指数级复杂度)
	public static int fib(int n){
		if(n==0)
		{
			return 0;
		}else if(n==1)
		{
			return 1;
		}else
		{
			return fib(n-1)+fib(n-2);
		}
	}
	//多项式发(线性复杂度)
	public static void fib1(int n){
		if(n==0){
			System.out.println(0);
		}
		int a[]=new int[n+1];
		a[0]=0;
		a[1]=1;
		System.out.println(a[0]);
		System.out.println(a[1]);
		for(int i=2;i<=n;i++){
			a[i]=a[i-1]+a[i-2];
			System.out.println(a[i]);
		}
		
	}
}