我编写了此代码..我需要得到最好的..我真的需要计算斐波纳契数的最佳性能..请帮助..
我已经阅读了一些这种类型的计算代码,并且我想我得到了其中的最好的。
为我实现这一点.. plz ..
ps:我真的需要BigInteger。.我将计算斐波那契数
ps2:我已经使用此算法计算了一些大数字,并且得到了不错的响应时间..但是我需要知道它是否会更好
ps3:要运行此代码,您将需要使用此VM参数-Xss16384k(StackSize)
-Xss16384k
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; } }
您的实现不适用于任何体面的数字,因为它会使堆栈溢出。
我看不出在这里使用递归的任何理由。递归很漂亮,但通常比较重(取决于语言)。这是一个带有简单for循环的有效实现:
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]; }
这是直接实现,而无需在文献中寻找有效的斐波那契算法。你最好找他们。
还要注意,这种基于缓存的实现会占用大量内存,并且只有多次调用该函数才有意义。