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(2 n ) .然后，您可以通过归纳来证明您的猜想。

基地:n = 1很明显

假设T(n-1) = O(2 n-1 ) , 因此

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

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

迭代版本

请注意，即使这个实现也只适用于较小的 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;