Вставить K элементов в отсортированный список из N элементов в O (klogk + n)

Question

Как мы можем вставить k новых элементов в отсортированный список размером n за время O (k log k + n)?

Я полагаю, что klogk может быть получен путем слияния сначала k элементов, а затем вставки ихв список размера n.Но мне не хватает (+ n) части.

Answer 1

Сначала мы можем отсортировать элементы, которые мы хотим вставить, это можно сделать с помощью алгоритма, подобного сортировка слиянием или куча сортировка, в O (k log k) .

Далее мы можем сделать слияние из двух списков (или любой тип структуры данных, если мы можем выполнить итерацию по ней в порядке возрастания).порядок).Это слияние может быть выполнено в O (k + n) , поскольку мы можем одновременно выполнять итерацию по двум спискам и каждый раз «выбрасывать» наименьший из двух и перемещать соответствующий курсор.

Например, для двух отсортированных массивов мы можем объединить их с:

public static int[] merge_sorted(int[] a, int[] b) {
    k = a.length;
    n = b.length;
    int[] c = new int[k+n];
    int ai = 0;
    int bi = 0;
    int ci = 0;
    while(ai < k && bi < n) {
        if(a[ai] <= b[bi]) {
            c[ci++] = a[ai++];
        } else {
            c[ci++] = b[bi++];
        }
    }
    while(ai < k) {
        c[ci++] = a[ai++];
    }
    while(bi < n) {
        c[ci++] = b[bi++];
    }
    return c;
}

Таким образом, сложность времени составляет O (k log k + k + n) , но эторавно O (k log k + n) .