Можно ли использовать O (1) или O (log n) для подсчета элементов и как это будет работать

Question

У меня есть задача, которая звучит так:

Пусть A будет отсортированным списком с n элементами. Мы хотели бы добавить некоторые элементы в A, чтобы весь список также сортировался.

(i) Дать O (n) -алгоритм, который добавляет O (1) элементов в A и возвращает отсортированный список.

(ii) Дайте O (n) -алгоритм, который добавляет O (log n) элементов в A и возвращает отсортированный список.

Я понимаю, как большие обозначения O можно использовать для описания сложности времени и пространства (и в задаче я предполагаю, что обе части требуют, чтобы сложность времени была O (n)), но в этой задаче, по-видимому, описывается величина элементов тоже. Это действительно трудно понять. Может кто-нибудь объяснить, как интерпретировать часть «O (1)» как часть «O (log n)»?

РЕДАКТИРОВАТЬ: Есть ли у вас какие-либо предложения, какой тип алгоритма мне следует использовать для завершить задания?

Answer 1

(i) вам нужно добавить O (1) элементов в A, означает, что вы добавляете постоянный элемент, то есть один элемент. Таким образом, вы можете добавить это, сначала создав связанный список из списка элементов, который будет O (n). Дальнейшее добавление узла путем перебора связанного списка в любой позиции будет O (n). Следовательно, общая сложность времени будет O (n).

Для справки: https://www.geeksforgeeks.org/given-a-linked-list-which-is-sorted-how-will-you-insert-in-sorted-way/

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

Таким образом, общее время сложность будет O (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;
}

Answer 2

Они описывают размер набора значений для добавления в список относительно его текущего размера N.