一尘不染

有没有比这更好的方法(性能)来计算斐波那契?

algorithm

我编写了此代码..我需要得到最好的..我真的需要计算斐波纳契数的最佳性能..请帮助..

我已经阅读了一些这种类型的计算代码,并且我想我得到了其中的最好的。

为我实现这一点.. plz ..

ps:我真的需要BigInteger。.我将计算斐波那契数

ps2:我已经使用此算法计算了一些大数字,并且得到了不错的响应时间..但是我需要知道它是否会更好

ps3:要运行此代码,您将需要使用此VM参数-Xss16384k(StackSize)

public class Fibonacci {

    private static BigInteger[] fibTmp = { BigInteger.valueOf(0), BigInteger.valueOf(1) };

    public static BigInteger fibonacci(long v) {

        BigInteger fib = BigInteger.valueOf(0);

        if (v == 1) {

            fib = BigInteger.valueOf(1);

        } else if (v == 0) {

            fib = BigInteger.valueOf(0);

        } else {

            BigInteger v1 = fibonacci(v - 1);
            BigInteger v2 = fibTmp[(int) (v - 2)];

            fib = v1.add(v2);
        }

        synchronized (fibTmp) {

            if (fibTmp.length - 1 < v)
                fibTmp = Arrays.copyOf(fibTmp, (int) (v + 10));

            fibTmp[(int) v] = fib;
        }

        return fib;
    }
}

阅读 251

收藏
2020-07-28

共1个答案

一尘不染

您的实现不适用于任何体面的数字,因为它会使堆栈溢出。

我看不出在这里使用递归的任何理由。递归很漂亮,但通常比较重(取决于语言)。这是一个带有简单for循环的有效实现:

private static BigInteger[] fibTmp = {BigInteger.ZERO, BigInteger.ONE};
private static int maxCached = 1;
public static BigInteger fibonacci(int v) {
    if (fibTmp.length<=v) {
        fibTmp = Arrays.copyOf(fibTmp, v*5/4);
    }
    for (; maxCached<v;) {
        maxCached++;
        BigInteger v1 = fibTmp[maxCached - 1];
        BigInteger v2 = fibTmp[maxCached - 2];
        fibTmp[maxCached] = v1.add(v2);
    }
    return fibTmp[v];
}

这是直接实现,而无需在文献中寻找有效的斐波那契算法。你最好找他们。

还要注意,这种基于缓存的实现会占用大量内存,并且只有多次调用该函数才有意义。

2020-07-28