Массивы Big O Notations с привязками к Linked List:
Согласно академической литературе для массивов она постоянна O (1), а для связанных списков она линейна O (n).
Массив принимает только одно умножение и сложение.
Связанный список, который не выложен в непрерывной памяти, требует обхода.
Этот вопрос заключается в том, что O (1) и O (n) точно описывают затраты на индексацию/поиск для массивов и связанных списков соответственно?
O(1) точно описывает вставку в конце массива. Однако, если вы вставляете в середину массива, вы должны перенести все элементы после этого элемента, поэтому сложность для вставки в этом случае составляет O(n) для массивов. End appending также дает скидку на случай, когда вам придется изменять размер массива, если он заполнен.
Для связанного списка вам нужно пройти по списку, чтобы сделать средние вставки, чтобы O(n). Вам не нужно перемещать элементы вниз.
Там хорошая диаграмма по википедии с этим: http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays
Linked list Array Dynamic array Balanced tree
Indexing Θ(n) Θ(1) Θ(1) Θ(log n)
Insert/delete at beginning Θ(1) N/A Θ(n) Θ(log n)
Insert/delete at end Θ(1) N/A Θ(1) amortized Θ(log n)
Insert/delete in middle search time
+ Θ(1) N/A Θ(n) Θ(log n)
Wasted space (average) Θ(n) 0 Θ(n)[2] Θ(n)
Предполагая, что вы говорите о вставке, где вы уже знаете точку вставки, то есть это не учитывает обход списка, чтобы найти правильную позицию:
Вставки в массиве зависят от того, где вы вставляете, поскольку вам нужно будет сдвинуть существующие значения. Наихудший случай (вставка в массив [0]) - O (x).
Вставка в список - O (1), потому что вам нужно только изменить следующие/предыдущие указатели смежных элементов.
Вставка для массивов, которые я предполагаю, медленнее. Конечно, вам нужно перебирать связанный список, но вам нужно выделить, сохранить и освободить память для вставки в массив.
В какой литературе вы ссылаетесь? Размер массива определяется при создании массива и никогда не изменяется после этого. Вставка действительно может выполняться только на свободных слотах в конце массива. Любой другой тип вставки может потребовать изменения размера, и это, конечно, не O(1). Размер связанного списка зависит от реализации, но он должен быть как минимум достаточно большим, чтобы хранить все его элементы. Элементы можно вставлять в любом месте списка, и поиск соответствующего индекса требует прохождения.
TL;DR несортированный массив аналогичен множеству. Как набор, элементы можно добавлять и удалять, перебирать и читать. Но, как и в случае с множеством, нет смысла говорить о вставке элемента в определенную позицию, потому что для этого будет попытка наложить порядок сортировки на то, что по определению является несортированным.
Согласно академической литературе для массивов она постоянна 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
Оператор присваивания задает значения массива явным порядком. Важно отметить, что назначение не совпадает с вставкой:
Несортированный массив не имеет порядка сортировки, и, следовательно, вставка не требует разрешения переопределения позиции. вставка - это не то же самое, что и назначение. Вставка массива просто определяется как:
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).
Давным-давно в системе с большим объемом оперативной памяти на этом диске я реализовал индексированный связанный список, который был проиндексирован, поскольку он был введен вручную или был загружен с диска. Каждая запись была добавлена к следующему индексу в памяти, а файл диска открыл запись, прикрепленную к завершению.
Программа кассовых аукционных продаж на компьютере модели я Radio Shack и записи на диск были только страховкой от сбоя питания и записи и архивирования, так как для удовлетворения временных ограничений данные должны были быть извлечены из оперативной памяти и напечатаны в обратный порядок, чтобы покупатель мог спросить, был ли первым, который пришел, последним, который он приобрел. Каждый покупатель и Продавец были связаны с последним проданным товаром, и этот предмет был связан с предметом, находящимся перед ним. Это был только один список ссылок, который был перемещен снизу вверх.
Исправления были сделаны с помощью записей с обратным знаком. Я использовал один и тот же метод для нескольких вещей, и я никогда не нашел более быструю систему, если бы этот метод работал для работы под рукой, и индекс был сохранен на диск и не нужно было перестраивать, поскольку файл перезагружается в память, как это могло бы быть сбой питания.
Позже я написал программу для редактирования более условно. Он также может реорганизовать данные, чтобы они были сгруппированы вместе.