使用分而治之的数组的第二大元素

Question

我写这个函数是为了找到数组中第二大的元素，但我对它的时间复杂度有些怀疑。 if 条件是否有 θ(1) 或它增加了递归调用的时间复杂度？

从实验的角度来看，它应该不大于具有分而治之策略时间复杂度的最大最大元素。

int secondmax(int arr[], int first , int last){
   if(first+1==last) return arr[first];
   int mid= first +(last-first)/2;
   int left = secondmax(arr, first, mid);
   int right = secondmax(arr, mid, last);
   if(  (left > right ? left : right) > max1){
      max2=max1;
      max1= left > right ? left : right;
   }

    else if((left > right ? left : right) > max2  &&     (left > right ? left : right) != max1){
       max2= left > right ? left : right;

   }
   return left > right ? left : right;
}

ps max1, max2 是全局变量，可能我可以砍掉 max1

Answer 1

if 放在递归调用前面时，在时间复杂度方面并不是一个重要的贡献者。给定您的算法，最重要的是在对时间复杂度的贡献方面使用递归完成的数组拆分。对你的算法做一个干运行可以让你看到你的算法将遵循以下递归方程：T(n) = 2T(n/2) + θ(1)。请注意，这里的 θ(1) 表示您在 2 个递归函数调用后编写的指令所消耗的时间单位。这个 θ(1) 和 no 一样。在递归调用之后，指令的数量是不变的。如果您使用了一个循环，其运行ning 时间取决于输入数组的长度，那么 θ(1) 就会出现，而不是 θ(1)。

那么，θ(1) 和 θ(n) 如何影响算法的复杂度？可以通过在递归方程中使用旧的 Master's Method 来简单地确定它。

对于 θ(1)，您的等式将是：T(n) = 2T(n/2) + θ(1) & 对于 θ(n)，它将变为 T(n) = 2T( n/2) + θ(n)。在对这两种情况应用马斯特定理后，您将获得最终时间复杂度，第一个为 θ(log n)，第二个为 θ(n [log n])。所以，这是您需要记住的主要区别。

使用分而治之的数组的第二大元素

Second greatest element of an array using divide and conquer

c

arrays

recursion

time-complexity

divide-and-conquer