c++ - 确定函数的复杂度(大O符号)

我在期中遇到了这个问题，我不确定我的答案是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);}

最佳答案

首先，我将您的代码加上另一个缩进

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)都要归功于for。尽管每次调用n都会减少，但是时间仍然受O(n)限制。

第二件事是计算recursiveFun1()会被调用多少次。显然(对我来说)它将被精确地称为n + 1次，直到参数n达到零值为止。

所以时间是n + (n-1) + (n - 2) + ... + 1 + 0这是((n+1)n)/2这是O(n^2)。

关于c++ - 确定函数的复杂度(大O符号)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33656996/