Временная сложность для удаления наименьшего значения в отсортированном массиве

#arrays #algorithm #data-structures #big-o #time-complexity

#массивы #алгоритм #структуры данных #big-o #сложность по времени

Вопрос:

Какова временная сложность удаления наименьшего значения из массива с n элементами, отсортированного от наименьшего к наибольшему?

Я считаю, что это O (1), потому что наименьшее значение является первым значением массива, это правильно?

Ответ №1:

Это O (n), потому что после удаления элемента все остальные элементы нужно переместить на 1 место влево.

Если бы у вас был связанный список, в этом не было бы необходимости, поэтому для этой структуры данных это было бы O (1) .

1. Массивы обеспечивают произвольный доступ, если вы помните 😉

2. Даже с одним связанным списком это O(1).

3. Я никогда не говорил, что это не так, но я все равно отредактировал свой ответ.

Ответ №2:

Чтобы удалить элемент из массива, вам сначала нужно его найти, что в вашем случае происходит O(1) потому, что: smallest = array[0]

Однако для его удаления потребуется переместить все элементы из n в n-1 , что потребует прохождения всего массива и перемещения элементов.

 int* removeSmallest(int *arr)
{
    //int smallest = arr[0]; // O(1)

    //shift elemts
    for(int i = 0; i < sizeof(arr)-1; i  ) // O(n)
    {
        arr[i] = arr[i 1];
    }

    return arr;
}