求配对法的时间复杂度

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）。