Является ли сложность времени вложения реализации списка приоритетных запросов O (n) отсортированного списка?

Question

От wikipedia:

Рассортировано реализация списка: Как кассу в супермаркете, но , где важные люди получают «вырезать» в перед менее важными людьми. (O (п) время вставки, O (1) получить, в следующий раз, O (N * Log (N)), чтобы построить)

Я думаю, если поиск позицию вставки с двоичным алгоритмом поиска , сложность времени ввода должна быть O (log (n)). Здесь я рассматриваю порядок поступления заданий как фактор приоритета.

Я тоже неправ или википедию?

Обновление: Согласно строгому определению списка из TAOCP:

Линейный список представляет собой последовательность п> = 0 узлы X 1, Х [2], ..., X [n], у которых существенные структурные свойства включают только относительные позиции между пунктами, как они появляются в строке .

Я предполагаю, что лист википедии см является не связанный список, и это может быть массив.

спасибо.

Answer 1

если связанный список поддерживается, вы не можете выполнять двоичный поиск так; Нахождение точки вставки O (n), Фактическая вставка - это O (1) при изменении соседних узлов, общий O (n).

если его массив поддерживается, вы можете выполнить двоичный поиск так; найти точку вставки О (журнал (п)), но вставки в массиве представляет собой О (п), как вы, возможно, придется перенести все элементы массива, общая О (п)

это почему у вас на самом деле есть дерево/куча, поэтому все операции могут быть O (log (n))

Answer 2

Похоже, что в вашей цитате Wikipedia ссылается на очередность приоритетов, поддерживаемую отсортированным списком, а не кучей. Для вставки элемента в отсортированный список требуется время O (n) (при условии, что мы сохраняем его сортировку).

Answer 3

Двоичный поиск действительно O(log n), но бинарный поиск работает на массивах - он работает в это время, потому что вы можете получить доступ к любому элементу в O (1).

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

Answer 4

Наихудшее время вставки в отсортированном списке - O (n). В худшем случае вставка наивысшего элемента в список. Для этого вам нужно пройти все элементы, а затем вставить в конец. Причина, по которой вы не можете выполнить двоичный поиск, состоит в том, что только элемент, доступ к которому вы можете получить в списке, является преемником вашего текущего элемента, то есть без произвольного доступа.

Answer 5

Википедия верна. Как уже указывали другие, списки не являются случайным доступом, поэтому вам нужно посетить каждый узел между A и B до того, как вы доберетесь до B. Это делает поиск в двоичном формате бесполезным, так как перемещение списка происходит из O (n), поэтому вы в конечном итоге делать больше работать, чем если бы вы просто перечислили один раз. Вы можете кэшировать начальный, средний и конечный узлы в отдельном буфере и сначала проверить их. Однако это будет иметь тот же эффект, что и использование нескольких списков. Структура данных пропущенных списков принимает эту идею еще на один шаг.

Так что вместо этого используйте кучу произвольного доступа или, возможно, список пропусков: http://en.wikipedia.org/wiki/Skip_list в зависимости от ваших потребностей.