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

Question

Из Википедия :

Реализация отсортированного списка: как касса в супермаркете, но где важные люди "врезаться" в фронт менее важных людей. ( О (п) время вставки, O (1) get-next time, O (n * log (n)) для сборки)

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

Так я не прав или Википедия неверна?

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

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

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

спасибо.

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

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

Answer 5

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