确定函数的复杂度（大O表示法）

Question

我在期中考试中遇到了这个问题，我不确定我的答案是O（n^2）。我想要有解释的答案，谢谢。

int recursiveFun1(int n)
{  for(i=0;i<n;i+=1) 
      do something;                                                                 
    if (n <= 0)
    return 1;
else
    return 1 + recursiveFun1(n-1);}

Answer 1

用输入的递归函数的执行时间表示。然后，如果n大于0，则执行以下操作：

• 假设“某物”有恒定的运行时间，它消耗c1*n时间

所以

R(n) = c1*n + c2 + R(n-1)

该方程有一个解，即O（n^2）。你可以通过归纳来证明，或者仅仅通过猜测一个形式为a*n^2 b*n c的解来证明。

注意：我假设“做点什么”有恒定的运行时间。这似乎是合理的。然而，如果它不是真的（例如，它包含一个递归调用），您的复杂性将更大-可能更大，这取决于“某物”正在做什么。

Answer 2

首先，我在代码中添加了另一个缩进

int recursiveFun1(int n)
{  
  for(i=0;i<n;i+=1) // this is bounded by O(n)
    do something; // I assume this part is O(1)

  if (n <= 0)
    return 1;
  else
    return 1 + recursiveFun1(n-1);
}

首先要说的是，每次调用recursiveFun1（）时，O（n）都是由于的而支付的。虽然每次调用时n都会减少，但时间仍以O（n）为界。

第二件事是计算将调用runsiveFun1（）的次数。显然（对我来说）它将被精确地调用n 1次，直到参数n达到零值。

所以时间是n（n-1）（n-2）。。。1 0是（（n 1）n）/2是O（n^2）。