如何返回时间,一个方法完成它的工作需要多少时间?

计算每次递归调用所需的时间,计算出有多少次递归调用,然后就有了答案。

计时是通过采取不同的 System.currenTimeMillis() System.nanoTime() 你要吃的东西前后。

我最终得到的可能不是一个最佳的解决方案,但以下是我得到的(可能它将来会帮助某人):

1) 我测量了时间,递归方法需要计算第42个(例如)斐波那契数。

2) 使用迭代方法,我计算了在使用递归方法计算第42个Fibonacci数时执行的程序行数。(行=3*fib_迭代(42)-2)

// Recursive algorithm, calculates Fibonacci number (slow)
private static double fib_recursive(int n){
    if( n <= 2) return 1;
    else return fib_recursive(n-1) + fib_recursive(n-2);
}

// Iterative algorithm, calculates Fibonacci number (fast)
private static double fib_iterative(int n){
    double a = 1, b = 1;
    for (int i = 2; i <= n; i++){
        b = a + b;
        a = b - a;
    }
    return a;
}

// Get time, which fib_recursive(int) needs to calculate the 400th Fibonacci number
private static long testRecursiveFor400(){
    int elapsedTime = 0;
    int start = (int) System.currentTimeMillis();
    fib_recursive(42);
    elapsedTime = (int) (System.currentTimeMillis() - start);
    return (3 * (long) fib_iterative(400) - 2) / ((3 * (int) fib_iterative(42) - 2) / elapsedTime);
}