Структуры данных, в которых Add, Get kth крупнейших являются O (log n) и O (1)

Question

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

Answer 1

Если бы я получил этот вопрос для интервью, я бы ответил, что мне неизвестно о каких-либо таких структурах данных, и я подозреваю, что они не существуют.Однако я подозреваю, что структуры данных, о которых думает интервьюер, представляют собой «отсортированный массив» и «список пропуска» соответственно.

Я бы тогда объяснил, что извлечение любого элемента массива по позиции равно O (1).Выяснить, где вставить это O (log (n)).Однако фактическая вставка O (n) из-за необходимости перемещения остальной части массива.Однако часть O (n) поставляется с очень хорошими константами.

Для списка пропуска извлечение равно O (log (n)).Вставка включает половину времени, изменяющего только один элемент, 1/4 времени редактирования 2, 1/8 времени редактирования 3 и т. Д., Что в среднем составляет 2 элемента.Это О (1).Однако вы не можете вставить элемент, не зная, куда его поместить.И этот поиск O (log (n)).(Чтобы сделать вставку истинно O (1), вам нужно либо собрать данные O (log (n)) для поиска, который вы сделаете доступным для вставки, либо создать моральный эквивалент двусвязного списка пропусков.)

Answer 2

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

Для экспертов: противник сначала добавляет n пунктов, отвечая на алгоритмы O (n) сравнений таким образом, чтобы оставить антицепь размером не менее log ² n. Затем он выбирает k таким образом, что вычисление get (k) заставляет алгоритм делать выборку для антицепи, что влечет за собой стоимость Ω (log ² n).

Почему противник может заставить такую ​​большую антицепь? Предположим, что алгоритм всегда не оставлял антицепи больше, чем log ² n элементов. По теореме Дилворта элементы могут быть разбиты не более чем на log ² n цепочек, которые можно объединить с помощью O (n log log n) сравнений, что дает алгоритм сортировки, который использует o (n log n) сравнений и, следовательно, противоречие.

Что мог иметь в виду ваш интервьюер? Для меня возможно, что если обе операции амортизируются, то есть решение. Однако это неканоническое ослабление требований.

Answer 3

Я полагаюсь на ответ @btilly, но я собираюсь попробовать другой способ описать структуру данных, которая имеет постоянное добавление и постоянную get (k). Это будет использовать много памяти, хотя.

Любая обратная связь приветствуется, я только придумываю это, пока иду вперед ...

Представьте, что мы говорим о наборе 8-битных целых чисел. Следовательно, существует 256 целых чисел, которые могут быть членами набора.

Теперь представьте сбалансированное бинарное дерево, содержащее все 256 целых чисел в виде листьев и 255 других неконечных узлов, что дает нам 9 уровней в целом. Форма этого дерева фиксирована, но мы будем хранить счетчик для каждого узла. Количество на каждом листовом узле будет просто равно 1 или 0, в зависимости от того, является ли это целое число членом нашего набора. Количество в каждом не-листовом узле будет суммой листьев под ним.

Это даст нам O (1) добавление (и удаление). Каждый раз при добавлении (или удалении) элемента ровно 9 узлов (корневой узел, соответствующий листовой узел и 7 промежуточных узлов) должны будут увеличивать (уменьшать) их счет.

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