Второй по величине элемент массива, использующий разделяй и властвуй

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) здесь указывает на постоянную единицу времени, потребляемую инструкциями, которые вы написали после двух вызовов рекурсивной функции.Это θ (1) будет таким же, как нет.инструкции постоянны после рекурсивных вызовов.Если бы вы использовали цикл, время выполнения которого зависело от длины входного массива, то вместо θ (1) на экране появилось бы θ (n).

Итак, как θ (1) и θ (n) влияют на сложность вашего алгоритма?Его можно просто определить, используя старый добрый метод Мастера в вашем уравнении повторения.

С θ (1) ваше уравнение будет иметь вид: T (n) = 2T (n / 2) + θ (1), а с θ (n) оно станет T (n) = 2T (n/ 2) + θ (n).После применения теоремы Мастера к обоим случаям вы получите конечную сложность времени как θ (log n) для первого и θ (n [log n]) для второго.Итак, вот главное отличие, которое вам нужно запомнить.