如何返回方法完成其工作所需的时间？

Question

我有一个简单的递归算法，它返回斐波那契数：

private static double fib_recursive(int n){
    if(n <= 2) return 1;
    else return fib_recursive(n-1) + fib_recursive(n-2);
}

现在我的任务是返回时间，该方法将用它来计算a上的第400个斐波那契数给定计算机，例如 fib_recursive(400)。 “Would”以粗体显示，因为我无法运行该函数，因为该方法需要很长时间才能给出答案。

如何才能最好地实现这一目标？

Answer 1

计算每次递归调用需要多少时间，算出有多少次递归调用，你就有了答案。

有更快的方法可以使用更智能的递归算法来实现此目的，但对于您的算法，只需输入一些计时信息即可。

Answer 2

通过在您想要测量的值之前和之后获取 System.currenTimeMillis() 或 System.nanoTime() 的差异来完成计时。

Answer 3

我最终得到的可能不是最好的解决方案，但这是我得到的（也许它会对将来的某人有所帮助）：

1）我测量了递归方法计算 42 次所需的时间（例如) 斐波那契数列。

2）使用迭代方法，我计算了用递归方法计算第42个斐波那契数时执行了多少程序行。 (Rows = 3*fib_iterative(42)-2)

3) 将 2. 除以 1。我得到了 1 毫秒内执行的平均行数。

4）使用迭代方法，我计算了用递归方法计算第400个斐波那契数时执行了多少程序行。 (行 = 3*fib_iterative(400)-2)

5) 将 4 除以 3。我得到了 fib_recursive(400) 花费的估计时间。

// 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);
}