0

次の関数のBig-Oランタイムとは何ですか？説明。

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

また、より高速なBig-Oランタイムでfib（int n）関数を繰り返し書き直すにはどうすればよいでしょうか。これはO（n）を使用する最良の方法でしょうか：

 public static int fibonacci (int n){
 int previous = -1;
 int result = 1;
 for (int i = 0; i <= n; ++i)
 {
 int sum = result + previous;
 previous = result;
 result = sum;
 }
 return result;
}
}
4

1 に答える 1

4

証拠

計算する時間関数を、計算する時間と計算する時間とそれらFib(n)を合計する時間の合計としてモデル化します（）。Fib(n-1)Fib(n-2)O(1)

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

この漸化式を（たとえば、母関数を使用して）解くと、答えが得られます。

または、再帰ツリーを描画することもできます。これにより、深みがnあり、この関数が漸近的であることが直感的にわかります。その後、誘導によって推測を証明することができます。O(2n)

ベース：n = 1明らかです

したがって、仮定しますT(n-1) = O(2n-1)

T(n) = T(n-1) + T(n-2) + O(1) これはに等しい

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

反復バージョン

フィボナッチ関数は指数関数的に増大し、32ビットの符号付きJava整数は最初の46個のフィボナッチ数しか保持できないため、この実装でさえnの小さな値にのみ適していることに注意してください。

int prev1=0, prev2=1;
for(int i=0; i<n; i++) {
  int savePrev1 = prev1;
  prev1 = prev2;
  prev2 = savePrev1 + prev2;
}
return prev1;
于 2012-07-28T03:03:35.310 に答える