フィボナッチ数を見つける最良の方法

Question

フィボナッチシリーズは0 1 1 2 3 5 8 ...などです。スワップ要素を使用して表示できますが、配列を使用して取得できます。私たちはここに複雑さが増加しているので、それは大きな数のスタックのための問題を発生さ

int fib(int n){ 
if(n<1) 
    return 1; 
else 
    return fib(n-1)+fib(n-2);} 

、それはそれのためのインタビューで再帰とメインロジックを使用して見つけるように頼まれました。では、ここで最適な方法は何ですか？

Answer 1

Memoization。それぞれの麻痺を1回だけ計算するロジックを作成します。

static BigInteger[] fibNumbs = new BigInteger[10000]; 


public static void main(String[] args) { 
     fibNumbs[1] = BigInteger.ONE; 
     fibNumbs[2] = BigInteger.ONE; 
     System.out.println(fibOf(10000)); 
    } 

public static BigInteger fibOf(int n) { 
     if (n <= 1) { 
      return BigInteger.ONE; 
     } 

     if (fibNumbs[n - 1]==null) { 
      fibNumbs[n - 1] = fibOf(n - 1); 
     } 

     if (fibNumbs[n - 2]==null) { 
      fibNumbs[n - 2] = fibOf(n - 2); 
     } 

     return fibNumbs[n - 1].add(fibNumbs[n - 2]); 
    } 

Answer 2

もし私があなたに2つの連続したフィボナッチ数、例えば、 a=3とb=5、あなたは次を推測できますか？ 2つの合計は8です。今度はa=5と新しく計算された数字b=8であなたは次を計算できますか？あなたは2つの最初の0、1の2つの反復を開始し、カウントダウンする回数のインデックスを表示します。ゼロになると、aが答えになります。これはO（n）アルゴリズムです。