より効率的なBigIntegerのフィボナッチ

Question

私はFib(n-1) + Fib(n-2)の再帰バージョンよりも効率的なフィボナッチを作成するためのクラスプロジェクトに取り組んでいます。このプロジェクトでは、BigIntegerを使用する必要があります。これまで私はマップを使用して以前のフィブス番号を格納する考えを持っていました。

public static BigInteger theBigFib(BigInteger n) { 

    Map<BigInteger, BigInteger> store = new TreeMap<BigInteger, BigInteger>(); 

    if (n.intValue()<= 2){ 
     return BigInteger.ONE; 

    }else if(store.containsKey(n)){   
     return store.get(n);  

    }else{ 
     BigInteger one = new BigInteger("1"); 
     BigInteger two = new BigInteger("2"); 
     BigInteger val = theBigFib(n.subtract(one)).add(theBigFib(n.subtract(two))); 
     store.put(n,val);   
     return val; 
    } 

} 

マップはそれ以上のものを格納していると思います。また、私はこのライン

BigInteger val = theBigFib(n.subtract(one)).add(theBigFib(n.subtract(two)));

が問題だと思います。誰かが私が間違ってやっていることや、基本的なコードよりも速くするための別の解決方法を明らかにすることができたら、 ありがとう！

Answer 1

コードの主な問題は、各関数呼び出しで新しいMapを作成することだと思います。あなたのメソッドがstaticであるにもかかわらず、まだローカル変数であることに注意してください。したがって、store.containsKey(n)の条件が成立せず、あなたのソリューションがナイーブではないことが保証されます。私。依然として指数関数的に複雑であるnを持っています。より正確には、答えに到達するまでには約​​のステップが必要です（基本的に、答えを構成するすべての「もの」が関数呼び出しによって返されるため）。

私は変数をローカル変数の代わりにstaticフィールドにすることをお勧めします。その後、呼数は指数関数ではなく線形になり、大幅な改善が見られます。他の解決策には、0,1,2からnまでフィボナッチ数を繰り返し計算する3つの変数を持つforループがあります。私が知っている最良の解は、実数での行列のべき乗または明示的な公式を含みますが、精度は悪いです。コンピュータサイエンスに適した質問StackExchangeのウェブサイト、imho。

Answer 2

BigIntegersのすべてを必要としない場合は、最後に2が必要です。

再帰的なソリューションではなく、ループを使用できます。

public static BigInteger getFib(int n) { 
    BigInteger a = new BigInteger.ONE; 
    BigInteger b = new BigInteger.ONE; 

    if (n < 2) { 
     return a; 
    } 
    BigInteger c = null; 
    while (n-- >= 2) { 
     c = a.add(b); 
     a = b; 
     b = c; 
    } 
    return c; 
} 

以前の値をすべて保存する場合は、代わりに配列を使用できます。

static BigInteger []memo = new BigInteger[MAX]; 
public static BigInteger getFib(int n) { 
    if (n < 2) { 
     return new BigInteger("1"); 
    } 

    if (memo[n] != null) { 
     return memo[n]; 
    } 

    memo[n] = getFib(n - 1).add(getFib(n - 2)); 
    return memo[n]; 
} 

---

あなただけの迅速かつ効率的なn番目のFib値をしたい場合。

フィボナッチのmatrix formを使用することができます。

A = 1 1 
    1 0 

A^n = F(n + 1) F(n) 
     F(n)  F(n - 1) 

Exponentiation by Squaringを使用すると、効率的にA^nを計算できます。