c - 确定以下函数的复杂性 (Big O)

Question

我需要帮助弄清楚这些功能的复杂性。在我看来，这些函数的大 o 将是 O(2^n)、O(n) 和 O(1)，但我不确定，所以如果我能得到任何帮助，我将不胜感激。

int func1(int n, int a, int b){
      
      int res=0;
    
      if (n == 1){
         res=a;
      }
    
      else{
        res=res+func1(n-1,a,b)+b;
      } 
    
      return res;
}


int func2(int n, int a, int b){
    
    int res = a;
    
    for (int i=0; i<n-1; i++){
        res+=b;
    }
    
    return res;
}


int func3(int n, int a, int b){
    
    int res = a + (n-1)*b;
    return res;
    
}

标签： cbig-o

Answer 1

您对＃2和＃3是正确的。

对于＃1，您可以稍微不同地看待它。您的代码可以重构为：

int func1(int n, int a, int b){   
      if (n == 1){
         return 0;
      }
      return func1(n-1, a, b) + b;    
}

这是一个明显的尾递归案例，可以直接转移到循环中（编译器经常这样做）：

int func1(int n, int a, int b){   
      int res = 0;
      while (n != 1) {
        n = n-1;
        res += b;
      }
      return 0 + res;
}

现在，这很明显，这O(n)与您的#2 非常相似。