java - 如何获得斐波那契递归的时间

Question

我有一个任务，他们给了我一个递归斐波那契算法并要求返回一个时间。我用 .SystemCurrentMilis 完成了它，并在下面发布了我的代码，但是测试人员说计算时间需要很长时间，所以我认为我必须给他们一些理论上的时间，因为执行函数和获取时间太长。希望对你们有所帮助。如何使函数 timetocompute 在任何情况下都能更快地工作。

import java.math.BigInteger;
import java.math.BigDecimal;

public class Fibonacci {

public BigDecimal timeToComputeRecursiveFibonacci(int n) {
    long startTime = System.currentTimeMillis();
    recursive(n);
    long finishTime = System.currentTimeMillis();
    long tempTime = finishTime - startTime;
    BigDecimal usedTime = BigDecimal.valueOf(tempTime);
    return usedTime;
}


public BigInteger recursive(int n) { 
    if (n <= 1)
        return BigInteger.valueOf(n);
    return recursive(n - 1).add(recursive(n - 2));
}

}

Answer 1

我为递归函数创建了一些测量。如果你想一想，如果你可以测量 recursive(n) 那么 recursive(n+1) 会慢近 2 倍，因为它需要计算函数n 和 n-1 也是如此。

• 第 n - 毫秒
• 30 - 25
• 31 - 43
• 32 - 70
• 33 - 113
• 34 - 196
• 35 - 301
• 36 - 513
• 37 - 926
• 38 - 1266
• 39 - 2210
• 40 - 3652

因此，您可以用 1.65^10*25 估算第 30 次的第 40 个数字，即 1.65^m*time(n)。这可以转换为年。我会尝试做这样的事情。