斐波那契数列

在求解这个函数的时候，我们最容易能想到递归，代码如下：

public static void main(String[] args) {


        long startTime = System.currentTimeMillis(); //程序开始记录时间

        System.out.println(Fibon(10));
        long endTime = System.currentTimeMillis(); //程序结束记录时间

        long TotalTime = endTime - startTime;//总消耗时间
        System.out.println(TotalTime);

    }
public static long Fibon(int n){
        if(n<=0)
            return 0;
        if(n==1)
            return  1;
        return Fibon(n-1)+Fibon(n-2);

}

但是在我们将n设为50的时候，就发现根本难以计算出来，因为在我们计算时，会有很多重复，而且随着数字的增大，计算量以几何数量增大，这时候，我们就要想一个好的算法

public static long Fibonaccif(int n){
       if(n==0)
           return 0;
       if(n==1)
           return 1;
       else{
        int[] f=new int[n+1];
        f[0]=0;
f[1]=1;
for(int j=2;j<f.length;j++)
{
    f[j]=f[j-1]+f[j-2];
}
return f[n];
    }
    }

这个方法虽然占用了数组的空间，但是，大大缩短了时间
当n=39时

而当n=45时

可以看到，递归用了6秒多，而循环只用了0，显而易见。