algorithm - 次のフィボナッチ数列のプログラムの時間計算量は? コードは動的計画法を使用します

Question

動的計画法を使用しない場合、再帰関係のマスター メソッドによると、複雑さが O(2 ^ n) になることがわかっています。 T(n) = T(n-1) + T(n-2). しかし、動的計画法を使用すると、それでも O( 2 ^ n) になりますか?

int [ ] fib = new fib [ 32 ] ;


int fibonacci ( int n) {

      if ( n == 1 ) return 1 ;

      if ( n == 2 ) return 1 ;

      // already calculated fibonacci (n)
      if ( fib [ n ] != 0) return fib [ n ] ;

      return fib [ n ] = fibonacci ( n−1 ) + fibonacci ( n − 2 ) ;

}

Answer 1

O(n)すでに計算されている場合は値を即座に返すため、それは単にになります。つまり、 のすべての値は、取得するfib(n)たびに 1 回だけ計算されnます。