Java中的Fibonacci序列耗时太长？ [英] Fibonacci Sequence in Java taking too long?

问题描述

我试图在Java中找到Fibonacci序列的总和，但运行时间过长（或者假设是？）。这会在我使用40以上的整数时减慢。

I'm trying to find the sum of the Fibonacci sequence in Java, but the run time is taking way too long (or is it suppose to?). This slows down anytime I use an integer past 40.

注意：在50时，会返回一个负值，令我难以理解。

Note: At 50, a negative value is returned which boggles my mind.

有什么建议吗？

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

推荐答案

n> 2 ，调用 getSum（n）以递归方式调用自身两次。每个调用都可以进一步递归。方法调用的总数按 2 ^ n 进行缩放， 2 ^ 50 是一个非常大的数字。这种不良的缩放反映了这样一个事实：简单的递归方法最终会不必要地重新计算相同的结果（例如fib（4））很多次，这就是为什么你的程序在增加 n 。

For n > 2, an invocation of your getSum(n) recursively invokes itself twice. Each of those invocations may recurse further. The total number of method invocations scales as 2^n, and 2^50 is a very large number. This poor scaling reflects the fact that the simple-minded recursive approach ends up needlessly recomputing the same results (e.g. fib(4)) a great many times, and it is why your program slows down so rapidly as you increase n.

超过数据类型 int的限制后，您获得的负返回值。您可以使用更宽的数据类型获得更大的限制，大概是 long 。如果这还不够，那么你需要去一些类似 BigInteger 的东西，而且会有很大的性能损失。

The negative return value you get after a certain point arises from exceeding the limits of data type int. You could get a larger limit with a wider data type, presumably long. If that's not enough then you would need to go to something like BigInteger, at a substantial performance penalty.

这篇关于Java中的Fibonacci序列耗时太长？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！