tldr несортированный массив аналогичен набору. Подобно набору, элементы можно добавлять и удалять, повторять и читать. Но, как и в случае с множеством, нет смысла говорить о вставке элемента в определенную позицию, потому что это будет попытка наложить порядок сортировки на то, что по определению не отсортировано.
Согласно академической литературе для массивов это постоянная O (1), а для связанных списков - линейная O (n).
Стоит понять, почему академическая литература цитирует вставку массива как O (1) для массива. Есть несколько концепций для понимания:
- Массив определяется как несортированный (если явно не указано иное).
Длина массива, определяемая как количество элементов, содержащихся в массиве, может быть произвольно увеличена или уменьшена за O (1) времени, и максимальный размер не ограничен массива.
(В реальном компьютере это не так, из-за различных факторов, таких как объем памяти, виртуальная память, пространство подкачки и т. Д. Но для целей алгоритма асимптотический анализ эти факторы не являются важно - мы заботимся о том, как время работы алгоритма изменяется при увеличении размера ввода до бесконечности, а не о том, как он работает на конкретном компьютере с определенным объемом памяти и операционной системой.)
Вставить и удалить равны O (1), поскольку массив является несортированной структурой данных.
Вставка не назначение
Подумайте, что на самом деле означает добавить элемент в несортированную структуру данных. Поскольку не существует определенного порядка сортировки, любой порядок на самом деле происходит произвольно и не имеет значения. Если вы думаете с точки зрения объектно-ориентированного API, сигнатура метода будет выглядеть примерно так:
Array.insert(Element e)
Обратите внимание, что это то же самое, что и методы вставки для других структур данных, таких как связанный список или отсортированный массив:
LinkedList.insert(Element e)
SortedArray.insert(Element e)
Во всех этих случаях вызывающая сторона метода insert не указывает, где вставляемое значение заканчивается хранением - это внутренняя деталь структуры данных. Кроме того, для вызывающей стороны не имеет смысла пытаться вставить элемент в определенном месте в структуре данных - для отсортированной или несортированной структуры данных. Для (несортированного) связанного списка этот список по определению не отсортирован, и поэтому порядок сортировки не имеет значения. Для отсортированного массива операция вставки по определению вставит элемент в определенную точку массива.
Таким образом, нет смысла определять операцию вставки массива как:
Array.insert(Element e, Index p)
При таком определении вызывающая сторона переопределяет внутреннее свойство структуры данных и налагает ограничение на порядок для несортированного массива - ограничение, которое не существует в определении массива, поскольку массив не отсортирован.
Почему это неправильное представление возникает с массивами, а не с другими структурами данных? Возможно, потому что программисты привыкли иметь дело с массивами, используя оператор присваивания:
array[0] = 10
array[1] = 20
Оператор присваивания присваивает значениям массива явный порядок. Здесь важно отметить, что назначение отличается от insert :
- insert : сохранить заданное значение в структуре данных без изменения существующих элементов.
- вставить в несортированный : сохранить заданное значение в структуре данных без изменения существующих элементов, и порядок поиска не важен.
- вставка в отсортированном виде : сохранить заданное значение в структуре данных без изменения существующих элементов, и порядок поиска важен.
- назначить [x] = v : перезаписать существующие данные в местоположении x с заданным значением v .
несортированный массив не имеет порядка сортировки, и, следовательно, insert не требует разрешения переопределения позиции. insert - это не то же самое, что assignment .Массив insert определяется следующим образом:
Array.insert(v):
array.length = array.length + 1
// in standard algorithmic notation, arrays are defined from 1..n not 0..n-1
array[array.length] = v
, что O (1).