Временная сложность хранения очереди приоритетов в виде двусвязного списка

Question

Если я хочу сохранить приоритетную очередь в виде отсортированного двусвязного списка, то не правильны ли следующие временные сложности?

• Вставить новую запись: O (n)

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

• Получить элемент с максимальным приоритетом: O (1)

  Я могу сохранить свой список отсортированным в порядке возрастания / убывания приоритета и сохранить заголовок и конец списка.Если это так, то получение элемента с максимальным приоритетом должно быть O (1), потому что мы знаем его местоположение.

• Удалить элемент с максимальным приоритетом: O (1)

  Та же логика, что и выше

Answer 1

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

Вы можете сделать выводздесь: «Вставить новую запись: O (n)»

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