Поиск временной сложности метода спаривания

Question

Мне нужно написать код, чтобы взять отсортированный двойной массив с нечетным числом элементов, найти пары значений с самым коротким расстоянием между ними и вернуть оставшееся значение, которое рассматривается как нечетный'. Ниже приведен код, который я написал, и он работает и возвращает правильное значение.

Может ли кто-нибудь помочь мне найти временную сложность алгоритма, который я использовал? Я попытался, но это действительно сбивает с толку.

public static Double findPairs(Double[] data, int i, int j, int k, int count) { 

    Double oddNumber = -1.; 

    if ((k < data.length) && (diff(data[i], data[j]) <= diff(data[j], data[k]))) { 
     data[i] = (-1.); 
     data[j] = (-1.); 
     if (k == data.length - 1) { 
      for (int c = 0; c < data.length; c++) { 
       if (data[c] != -1.) { 
        i = c; 
        break; 
       } 
      } 
      if (i != k) { 
       for (int c = 0; c < data.length; c++) { 
        if ((c > i) && (data[c] != -1.)) { 
         j = c; 
         break; 
        } 
       } 
       findPairs(data, i, j, k, count + 1);      
      } 
     } 
     else { 
      for (int c = 0; c < data.length; c++) { 
       if (data[c] != -1.) { 
        i = c; 
        break; 
       } 
      }  
      for (int c = 0; c < data.length; c++) { 
       if ((c > i) && (data[c] != -1.)) { 
        j = c; 
        break; 
       } 
      }  
      for (int c = 0; c < data.length; c++) { 
       if ((c > j) && (data[c] != -1.)) { 
        k = c; 
        break; 
       } 
      } 
      findPairs(data, i, j, k, count + 1); 
     } 
    } 
    else if ((k < data.length) && (diff(data[i], data[j]) > diff(data[j], data[k]))) { 
     if (k == data.length - 1) { 
      data[j] = (-1.); 
      data[k] = (-1.); 
     } 
     else { 
      i = j; j = k; 
      for (int c = 0; c < data.length; c++) { 
       if ((c > j) && (data[c] != -1.)) { 
        k = c; 
        break; 
       } 
      } 
      findPairs(data, i, j, k, count); 
     } 
    }  
    for (int c = 0; c < data.length; c++) { 
     if (data[c] != -1) { 
      oddNumber = data[c]; 
     } 
    } 
    return oddNumber; 
} 

Алгоритм: вы начинаете с первого, второго и третьего элементов массива. Сравните различия между первым и вторым элементами, а также вторым и третьим элементами. Если первое различие меньше или равно последнему, сделайте первые два элемента (-1). В противном случае сделайте то же самое для второго, третьего и четвертого элементов. Продолжайте этот процесс. Всякий раз, когда первое различие меньше второго разницы, сделайте относительные элементы (-1) и выполните поиск с начала массива для элементов, которые не являются (-1). Повторите процесс, начиная с первых трех элементов, которые вы найдете. Всякий раз, когда второе различие меньше первого, держите первый элемент из трех в стороне и проверяйте со следующими тремя. Сделайте это, пока не достигнете конца массива.

Answer 1

Как вы сформулировали алгоритм и написал свой код, в худшем случае вы можете перебирать все больше и больше списка, поскольку алгоритм переходит от поиска одной пары к следующей, которая будет установлена ​​на -1 , Таким образом, в худшем случае время работы O (n^2).