0

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

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

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

怎样才能最好地实现？

4

3 回答 3

3

计算每次递归调用的时间，计算出递归调用的次数，你就有了答案。

有更快的方法可以做到这一点，使用更智能的递归算法，但对于您的算法，只需输入一些时间信息。

于 2010-09-20T19:27:09.733 回答
1

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

于 2010-09-20T19:55:21.500 回答
0

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

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

2）使用迭代的方法，我用递归的方法计算第42个斐波那契数时，计算了执行了多少程序行。（行 = 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);
}
于 2010-09-20T22:11:54.423 回答