c++ - 如何找到给定代码的时间复杂度？

Question

我们需要找出给定数组中的最大不相邻子集和，

no-adjacent：我们不能在形成最大子集和时选择相邻元素。

例如：

arr = [5, 3, 7, 14]

解 : [5, 14] : 19 最大和

说明：

5和14不是相邻的数字，它们的和最大。

代码

int main(){

   //input
   int n;
   cin>>n;
   vector<int> arr;
   while(n--){
      int x;
      cin>>x;
      arr.push_back(x);
   }

   int max_adj = INT32_MIN;

   for (int i = 0; i < arr.size(); i++)
      max_adj = max(max_adj, maxSum(arr, i));

 }


int maxSum(vector<int> &arr, int vidx) {

   if (vidx >= arr.size()) {
       return 0;
   }

   int max_ = 0;

   for (int i = vidx + 2; i < arr.size(); i++) {
       max_ = max(max_, maxSum(arr, i));
   }

   return max_ + arr[vidx];
}

上述方法是解决此问题的蛮力/天真的递归方法。我知道存在更好的dp解决方案。

但是，我只是在寻找一种方法来找出

大 O 时间复杂度

这个递归解决方案的数学。

标签： c++mathtime-complexity