java - fib 递归的大 O 表示法

Question

以下函数的 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;
}
}

Answer 1

证明

您将要计算的时间函数建模为要计算的时间加上要计​​算的时间加上将它们加在一起的时间的总和 ( 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)

迭代版本

请注意，即使这种实现也只适用于 n 的小值，因为 Fibonacci 函数呈指数增长，并且 32 位有符号 Java 整数只能保存前 46 个 Fibonacci 数

int prev1=0, prev2=1;
for(int i=0; i<n; i++) {
  int savePrev1 = prev1;
  prev1 = prev2;
  prev2 = savePrev1 + prev2;
}
return prev1;