Java 中的斐波那契数列耗时太长？

Question

我试图在 Java 中找到斐波那契数列的总和，但是运行时间太长了（或者应该如此？）。每当我使用超过 40 的整数时，速度都会变慢。

注意：在 50 时，返回了一个负值，这让我很困惑。

有什么建议吗？

public static void main(String[] args) {        
    //Find Fibonacci sequence
    int sum=getSum(50);
    System.out.println("Sum of Fibonacci Numbers is " + sum); 
}
static int getSum(int n){
    if (n==0) return 0;
    if (n==1 || n==2) return 1;
    else return getSum(n-1) + getSum(n-2);
}

Answer 1

如果要计算第 50 个斐波那契数，则需要使用 long 而不是 int。第50个斐波那契数为12586269025，超过了int的最大值（见http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html）

非递归算法可能会更快，请参阅 http://planet.jboss.org/post/fibonacci_sequence_with_and_without_recursion 了解不同的实现。

Answer 2

对于 n > 2，对 getSum(n) 的调用会递归调用自身两次。这些调用中的每一个都可以进一步递归。方法调用的总数按 2^n 缩放，2^50 是一个非常大的数字。这种糟糕的缩放反映了这样一个事实，即头脑简单的递归方法最终不必要地多次重新计算相同的结果（例如 fib(4)），这就是为什么你的程序在你增加时速度如此之快的原因 n .

在某个点之后得到的负值return是由于超出了数据类型的限制int。您可以使用更广泛的数据类型获得更大的限制，大概是 long。如果这还不够，那么您将需要执行 BigInteger 之类的操作，但性能会大幅下降。

Answer 3

如果您想保持递归方法不变，请将计算结果缓存在数组或映射中。当您为 n 计算出一个斐波那契时，保存该结果。然后，在您的方法中，首先查看您是否有结果，如果有，return。否则，进行递归调用。下面是一个例子：仍然使用递归并且它非常快：

public static Map<Long,Long> cache = null;

public static void main(String[] args) {
    cache = new HashMap<Long,Long>();
    cache.put(0L,0L);
    cache.put(1L,1L);
    cache.put(2L,1L);
    Long sum=getSum(50L);
    System.out.println("Sum of Fibonacci Numbers is " + sum); 

}

static Long getSum(Long n){
    if (cache.containsKey(n)) { return cache.get(n); }
    else {
        Long fib = getSum(n-1) + getSum(n-2);
        cache.put(n, fib);
        return fib;
    }
}

Answer 4

首先，使用 long 而不是 int，以避免溢出。

其次，使用非递归算法，因为我认为递归算法存在于指数时间内。一个设计良好的非递归算法将在线性时间内解决（我认为）。

非递归示例

static long getSum(int n){

    long[] fibonacci = new long[n];
    fibonacci[0] = 1;
    fibonacci[1] = 1;

    if (n==0) return 0;
    if (n==1 || n==2) return 1;

    for(int i = 2; i < n;i++){
        fibonacci[i] = fibonacci[i-1]+ finonacci[i-2];
    }
    return fibonacci[n-1];
}

我还没有测试过，但应该可以。

如果您打算经常调用此方法，谨慎的做法是将数组存储在该方法之外，以便在执行此操作时进行简单的查找。这将为已经至少计算过一次的数字提供一个恒定时间的解决方案。下面是一个例子。

static long[] fibonacci= {1,1};
static long getSum(int n){

    if (n==0) return 0;
    if (n==1 || n==2) return 1;

    int old_length = fibonacci.length;

    if(fibonacci.length < (n-1)){
        fibonacci = Arrays.copyOf(fibonacci,n);
    }else{
        return fibonacci[n-1];
    }



    for(int i = old_length; i < n;i++){
        fibonacci[i] = fibonacci[i-1]+ finonacci[i-2];
    }
    return fibonacci[n-1];
}

同样，该示例未经测试，因此可能需要进行一些调试。

这里是算法的线性时间实现，它使用常数开销，而不是线性开销。

static long getSum(int n){

    long currentNum = 0;
    long previousNum = 1;
    long previousNum2 = 1;

    if (n==0) return 0;
    if (n==1 || n==2) return 1;

    for(int i = 2; i < n;i++){
        currentNum = previousNum+ previousNum2;
        previousNum2 = previousNum;
        previousNum = currentNum;
    }
    return currentNum;
}

Answer 5

正如其他人已经指出的那样，您应该使用 long 作为计算出的斐波那契值，因为数字会很快变得很长。

如果您最优先考虑的是性能，您可以使用以下公式：

（思想取自线性代数讲座，实际公式取自 Wikipedia。）
这样你就可以在常数时间内得到第n个斐波那契数（取决于公式中n次方的计算）。

以下代码计算前 93 个数字的斐波那契数列，没有等待时间（在我的机器上）：

private static final double SQRT_FIVE = Math.sqrt(5);
private static final double GOLDEN_RATIO = (1 + SQRT_FIVE) / 2;

public static void main(String[] args) {
    for(int i = 0; i <= 92; i++) {
        System.out.println("fib(" + i + ") = " + calculateFibonacci(i));
    }
}

public static long calculateFibonacci(int n) {
    double numerator = Math.pow(GOLDEN_RATIO, n) - Math.pow(1-GOLDEN_RATIO, n);
    double denominator = SQRT_FIVE;

    // This cast should in general work, as the result is always an integer. 
    // Floating point errors may occur!
    return (long)(numerator/denominator); 
}

从第94个数开始，long已经不够用了，需要用BigInteger和拟合数学运算，double计算这么大的数可能会产生计算错误。

Answer 6

递归解决方案不一定很慢。如果您要使用这种尾递归解决方案，您将节省大量内存并仍能获得极快的速度（例如 Fib(10000) 在我的机器上以 1.1 秒的速度运行）。

此处 n 是您计算斐波那契数列的序号，而 f0 和 f1 是两个累加器，分别对应之前和当前的斐波那契数。

public class FibonacciRec {
    public static int fib(int n, int f0, int f1) {
        if (n == 0) {
            return f0;
        } else if (n == 1){
            return f1;
        } else {
            return fib(n-1, f1, f0+f1);
        }
    }

    public static void main(String[] args) {
        System.out.println(fib(10, 0, 1));
    }
}

Java 中的斐波那契数列耗时太长？

Fibonacci Sequence in Java taking too long?

java

fibonacci