有沒有比這個更好的方法（性能）計算斐波那契？

Question

我做這個代碼..我需要得到最好的..我真的需要計算斐波那契數字的最佳性能..請幫助..

我讀過這種類型的代碼計算，我認爲我得到了他們最好的..

Avaliate這對我來說.. 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; 
    } 
} 

Answer 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]; 
} 

這就是不看在文學高效的斐波那契算法的直接實現。你最好找他們。

還要注意，這種基於緩存的實現是內存昂貴，並且只有在多次調用函數時纔有意義。

Answer 2

首先，您正在使用遞歸，在時間和空間複雜度方面效率都不高。你應該使用迭代方法。

然後，如果額外的內存或空間不是交易斷路器，並且性能確實很關鍵，那麼您可能需要預先計算所有稍後想要計算的數字，並將它們存儲在數組或磁盤中你的記憶太多了。稍後，您可以在不變的時間獲得價值。

Answer 3

是的，還有更好的方法。這是log(n)經過測試且非常有效的方法，用於計算任意精度的斐波納契值，給定正整數作爲輸入。該算法是從解決方案適用於SICP的exercise 1.19：

public static BigInteger fibonacci(int n) { 

    int count = n; 
    BigInteger tmpA, tmpP; 
    BigInteger a = BigInteger.ONE; 
    BigInteger b = BigInteger.ZERO; 
    BigInteger p = BigInteger.ZERO; 
    BigInteger q = BigInteger.ONE; 
    BigInteger two = new BigInteger("2"); 

    while (count != 0) { 

     if ((count & 1) == 0) { 
      tmpP = p.multiply(p).add(q.multiply(q)); 
      q = two.multiply(p.multiply(q)).add(q.multiply(q)); 
      p = tmpP; 
      count >>= 1; 
     } 

     else { 
      tmpA = b.multiply(q).add(a.multiply(q).add(a.multiply(p))); 
      b = b.multiply(p).add(a.multiply(q)); 
      a = tmpA; 
      count--; 
     } 

    } 

    return b; 

} 

在本書的聯動章節有它的工作原理（向下滾動行使1.19）的解釋，它指出：

這是一個巧妙的算法，用於計算對數步數中的斐波那契數...此練習由Joe Stoy提出，基於Kaldewaij，Anne的一個示例。 1990. 編程：算法的推導。

當然，如果相同的值需要使用地圖存儲以前的值進行計算過一遍又一遍，進一步的性能提升可以通過已經被計算memoizing結果來實現，例如。