Какова сложность этой программы?

Question

Я хочу проанализировать сложность времени выполнения программы ниже. Пожалуйста, ответьте на объяснение.

private static void printSecondLargest(int[] arr) { 
    int length = arr.length, temp; 
    for (int i = 0; i < 2; i++) { 
     for (int j = i+1; j < length; j++) { 
      if(arr[i]<arr[j]) { 
       temp = arr[i]; 
       arr[i] = arr[j]; 
       arr[j] = temp; 
      } 
     } 
    } 
    System.out.println("Second largest is: "+arr[1]); 
} 

Answer 1

Это O (п), где п представляет длину массива.

Тело внутреннего контура большего:

if(arr[i]<arr[j]) { 
    temp = arr[i]; 
    arr[i] = arr[j]; 
    arr[j] = temp; 
} 

работает в постоянное время.

Этот код будет выполнен в начале arr.length-1 раз, затем arr.length-2 раз. Это 2 * arr.length - 3. Таким образом, время выполнения пропорционально 2n-3, которое равно O (n).

Answer 2

Внешний контур будет работать в два раза и внутренние трассы контура (длина-1) и второй раз (длина-2)

предположим, что длина N

so it will be 2*((N-1)/2+(N-2/)2)==2*(2n-3)/2

Which is final (2N-3) and in O notation it is O(N) 

Answer 3

private static void printSecondLargest(int[] arr) {  
    int length = arr.length, temp; // **it takes contant time** 
    for (int i = 0; i < 2; i++) {  // as loop goes only two step it also takes constant time 
     for (int j = i+1; j < length; j++) { // this loop takes n time if we consider arr length of size n 
      if(arr[i]<arr[j]) { 
       temp = arr[i]; // it also takes constant time 
       arr[i] = arr[j]; 
       arr[j] = temp; 
      } 
     } 
    } 
    System.out.println("Second largest is: "+arr[1]); 
} 

Таким образом, в соответствии с приведенным выше вычислением мы пренебрегаем постоянным временем и вычисляем все переменные временные ограничения, а в зависимости от сложности кода будет O(n).

Answer 4

Очевидно, что O (n). Внешний цикл работает только 2 раза и внутренний цикл N раз. Таким образом, общая сложность O (2 * n).