斐波那契数列

斐波纳挈数列，尽量用for循环实现而不是用递归。递归的效率低的吓人！

Main方法实现：

写道

public static void main(String[] args){
    int n = Integer.parseInt(args.length == 0 ? "1" : args[0]);

    long t0 = System.currentTimeMillis();

    long fb = fib(n);
    System.out.println("fb= " + fb);

    long t1 = System.currentTimeMillis();
    System.out.println("t1 - t0 :" + (t1 - t0) );

    long fbFor = fibFor(n);
    System.out.println("fbFor= " + fbFor);

    long t2 = System.currentTimeMillis();
    System.out.println("t2 - t1 :" + (t2 - t1) );
}

 递归函数：

写道

static long fib(int n){
    if(n <= 2)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

 For循环实现：

写道

static long fibFor(int n){
    long fib = 1;
    long f1 = 1;
    long f2 = 1;

    for(int i = 3; i <= n; i++){
        fib = f1 + f2;
        f1 = f2;
        f2 = fib;
   }

   return fib;
}

 

在本机测试,n = 44:t1-t0=16789ms, t2-t1= 0ms