0

我知道，如果我不使用动态编程，根据递归关系的主方法，复杂度将是 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 ) ;

}
4

2 回答 2

2

它将是 just O(n)，因为如果它已经被计算，你会立即返回一个值。这意味着，对于每个您将拥有的每个值，fib(n)都将只计算一次。n

于 2013-09-28T15:14:51.000 回答
1

正如dreamzor 已经说过的那样，复杂性将是O(n)因为如果您使用已经计算的值调用斐波那契，您将停止递归。他是100%正确的。

但是，更有趣的是，函数的调用次数fib实际上是2*n - 3for n > 1。实验上，很容易验证：您可以简单地添加一个counter在函数中递增的全局变量，fib然后打印它。

这是因为对于n尚未计算的每个，您将执行 2 次递归调用（n=1 或 2 除外）。

现在，有点跑题了，但是稍微重构一下代码：

int fibonacci (int n) {
      if (n == 1 || n == 2) {
          fib[n] = 1;
      } else if (fib[n] == 0) {
          fib[n] = fibonacci(n - 1) + fibonacci (n - 2);
      }

      return fib[n];
}

另外，我知道您可能正在编写此函数以便学习，但您必须知道迭代形式或尾递归会更好。

于 2013-09-28T16:37:11.127 回答