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

标签 java recursion fibonacci

我有一个任务，他们给了我一个递归斐波那契算法并要求返回一个时间。我用 .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));
}

}

最佳答案

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