Почему операция «удалить» на отсортированном массиве считается «медленной»?

Question

В настоящее время я изучаю алгоритмы и структуры данных с помощью знаменитого Стэнфордского курса Тима Рафгардена. В видео 13-1 при объяснении сбалансированных двоичных деревьев поиска он сравнил их с отсортированными массивами и упомянул, что мы не выполняем удаление в отсортированном массиве, потому что он слишком медленный (я полагаю, он имел в виду "медленный по сравнению с другими операциями, что мы можем работать за постоянное время [Select, Min / Max, Pred / Succ], O (log n) [Search, Rank] и O (n) [Output / print] time ").

Я не могу перестать думать об этом заявлении. А именно, я не могу обдумать следующее:

Допустим, нам дана статистика порядка c или значение элемента, который мы хотим удалить из отсортированного (по возрастанию) массива.

Мы, безусловно, можем найти его позицию в массиве, используя Select или Search за постоянное время или время O (n) соответственно.

Затем мы можем удалить этот элемент и перебирать элементы справа от удаленного one, увеличивая их индексы на единицу, что займет время O (n). [это я (возможно, безуспешно) пытаюсь описать операцию «переместить каждую из них на 1 позицию влево»]

Вся операция займет линейное время - O (n) - в худшем случае.

Основной вопрос - Неправильно ли я думаю? Если нет, то почему это считается медленным и нежелательным?

Answer 1

Вы правы: удаление из массива происходит медленно, потому что вам нужно переместить все элементы после него на одну позицию влево, чтобы вы могли закрыть созданное вами отверстие.

Учитывается ли O(n) медленный зависит от ситуации. Удаление из массива, скорее всего, является частью более крупного и сложного алгоритма, например, внутри al oop. Это добавит коэффициент n к вашей окончательной сложности, что обычно плохо. Использование дерева только добавит коэффициент log n, а O(n log n) будет намного лучше, чем O(n^2) (асимптотически).

Answer 2

Оператор относится к определенной структуре данных c, которая используется для хранения отсортированных значений: отсортированный массив. Эта специфическая структура данных c будет выбрана для простоты, для эффективного хранения и для быстрого поиска, но она медленная для добавления и удаления элементов из структуры данных.

Другие структуры данных, которые содержат отсортированные значения, могут быть выбрано. Например, двоичное дерево, или сбалансированное двоичное дерево, или tr ie. Каждый из них имеет разные характеристики с точки зрения производительности и эффективности хранения, и будет выбран в зависимости от предполагаемого использования.

Сортированный массив медленно добавляется и удаляется, потому что в среднем эти операции требуют сдвига половины массив, чтобы освободить место для нового элемента (или, соответственно, заполнить пустую ячейку).

Однако на многих архитектурах простота структуры данных и скорость сдвига означают, что структура данных отлично подходит для "небольших" наборов данных.