Сложность времени вставки Java PriorityQueue (кучи) из n элементов?

Я хотел бы знать, какова временная сложность Java PriorityQueue.Add() для n элементов.

Я понимаю, что потенциальная вставка одного элемента в худшем случае - это O(log(n)), но мне не ясно, какова временная сложность для вставки набора из n элементов?

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

Примечание. Меня интересует только худший случай, а не амортизация.

Этот вопрос предполагает, что существует логический способ описания процесса заполнения структуры данных (кучи) n элементами, который отличается от простого рассмотрения n x log(n) вставок по отдельности.

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


java time-complexity heap priority-queue
person James Wierzba    schedule 21.11.2017    source источник
comment
парень ниже играет с вашим неправильным определением. с временной сложностью вставки в структуры данных обычно означает, что если у вас есть n элементов в структуре, какова временная сложность вставки в нее 1 элемента. вы сказали вставить n элементов. вы не можете вставить меньше n, если хотите вставить n.   -  person MarianP    schedule 21.11.2017
comment
@MarianP Нет ли стандартного логического способа описать процесс заполнения структуры данных элементами n? Это довольно распространенный сценарий.   -  person James Wierzba    schedule 22.11.2017
comment
@pjs да, вы правы, это дубликат. Я добавлю свой голос, чтобы закрыть и указать на существующий вопрос   -  person James Wierzba    schedule 22.11.2017

Ответы (2)


arrow_upward
6
arrow_downward

В общем случае это O(N log N). Алгоритм O(N) существует для особого случая, когда ввод уже упорядочен, но он не предусмотрен в java.util.PriorityQueue.

person user207421    schedule 21.11.2017
comment
Интересно, что существуют более сложные методы сортировки за линейное время, предполагающие, что ввод имеет определенный тип, некоторые из них упоминаются в этом сообщении: stackoverflow.com/questions/749585/sorting-in-linear-time - person gue; 22.11.2017
comment
@gue О да. Например, если вход уже находится в правильном порядке PQ, это просто pq.a[i++] = input.nextElement(). - person user207421; 22.11.2017
comment
Предварительно отсортированные данные не требуются, есть алгоритм Theta(n), который работает с любым набором данных. Смотрите связанный ответ. - person pjs; 22.11.2017
comment
Как насчет: log 1, log 2... log N для вставки 1-го, 2-го, .... N-го элемента? лог 1 + лог 2 + ... + лог N = лог N! - person Vyshnav Ramesh Thrissur; 07.03.2021

arrow_upward
17
arrow_downward

Кажется, что вставка n элементов должна быть O (n log n)

Java PriorityQueue (Java Doc< /а>)

O(log n) время для методов постановки в очередь и удаления из очереди (предложение, опрос, удаление() и добавление)

O (n) для методов удаления (объект) и содержит (объект)

O(1) для методов поиска (взгляд, элемент и размер)

Все эти временные сложности кажутся наихудшими (вики), за исключением .add(). Вы правы, ставя под сомнение границы, поскольку документ Java также указывает на расширение этой несвязанной структуры:

Детали политики роста не уточняются

Как они также утверждают в документе, PriorityQueue основан на массиве с определенной начальной емкостью. Я бы предположил, что рост будет стоить O (n) времени, что также будет наихудшей временной сложностью для .add().

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

PriorityQueue(int initialCapacity)

РЕДАКТИРОВАТЬ: Заявление о времени O (n) для строительства верно (как указано @pjs в комментариях). Эта процедура часто называется heapify и работает с предварительно существующим массивом, который используется для построения бинарное дерево на нем за время O(n).

person gue    schedule 21.11.2017
comment
Извините, но ваша интуиция (и, следовательно, ваш ответ) неверна в отношении построения кучи. Я пометил это как дубликат, вы можете найти там правильный ответ вместе с несколькими ссылками на источники и доказательства. - person pjs; 22.11.2017
comment
Спасибо за ваш отзыв, я изменил эту часть своего ответа. Я не считаю это дубликатом, поскольку вопрос связан с методом .add() конкретного контейнера Java, а не с построением общей кучи. - person gue; 22.11.2017