Упорядоченный словарь, поддерживающий ключ уменьшения?
Многие очереди с быстрым приоритетом (такие как куча Фибоначчи и куча сопряжения) поддерживают операцию уменьшения ключа, которая принимает элемент, уже сохраненный в очереди приоритетов, и эффективно снижает его приоритет. В случае кучи Фибоначчи и связывания ключ уменьшения может быть выполнен быстрее, чем удаление элемента из очереди приоритетов и последующая его повторная вставка.
Мне интересно, может ли подобная операция поддерживаться в упорядоченных словарных структурах (бинарные деревья поиска, скиплисты и т. Д.). В частности, предположим, что у меня есть упорядоченный словарь и я хочу изменить ключ некоторой пары ключ / значение на другой ключ. Можно ли сделать это за время O(1) или O(log log n) в любом стандартном представлении упорядоченного словаря? Мне любопытно, потому что при сбалансированном BST это можно сделать за O(log n), удалив элемент и заново вставив его, но кажется, что может быть более быстрый способ сделать это.
Спасибо!
2 ответа
Представьте себе следующий сценарий:
Вы начинаете N элементов. Сейчас,
- Вы создаете "упорядоченный словарь" размером N, содержащий N копий некоторого значения X, большего, чем любой элемент.
- Затем вы вызываете клавишу уменьшения на каждом X, изменяя его на один из N реальных элементов.
- Пройдите по словарю, читая элементы по порядку.
В большинстве реализаций упорядоченных словарей шаги 1 и 3 занимают O (N) времени. Если клавиша уменьшения занимает время O (1) или O (log log N), то шаг 2 занимает время O (N) или O (N log log N). Это означает, что вы можете сортировать за O (N) или O (N log log N).
По нижнему пределу O (N log N) для сортировки на основе сравнения это означает, что вы НЕ МОЖЕТЕ делать нажатие клавиши уменьшения времени O (1) или O (N log log N), если только
- ваш заказной словарь НЕ основан на сравнениях (что обычно происходит, если вы знаете что-то особенное об элементах, например, все они находятся в диапазоне 1-100), или
- Ваш заказной словарь НЕ поддерживает шаги 1 и 3 за O (N) время (что исключает все обычные подозреваемые, такие как BST или пропускаемые списки).
Сортированный массив или отсортированный связанный список поддерживает O(1) клавиша уменьшения или увеличения (при условии отсутствия / минимальных дубликатов, см. 4-й параграф). Это потому, что, если вы подумаете об этом, вам нужно будет не более двух элементов поменять местами для операции уменьшения или увеличения.
Не лучшие структуры данных на практике (хотя они имеют свое место), но все же ответ.
Единственное ограничение заключается в том, что для начала вам нужен указатель на узел, потому что он уже займет O(log n) а также O(n) соответственно просто найти узел.
Если есть дубликаты, ход может занять худший случай O(n) для обоих (если большинство значений одинаковы), что довольно плохо. Однако для связанного списка должно быть возможно получить O(1) имея некоторый связанный список связанных списков, где каждый узел в большом связанном списке представляет определенное значение, а каждый связанный список представляет все узлы, равные этому значению.
Мой оригинальный ответ о том, почему не работает BBST или список пропусков:
(не удаляю, потому что, кажется, стыдно идти впустую)
В худшем случае меньше чем O(log n) перемещение по одному элементу невозможно для BBST или списка пропусков, хотя, насколько я могу судить, это будет по меньшей мере так же эффективно, как и повторная вставка. Средний случай, вероятно, меньше, чем O(log n),
Мы ищем это - поиск, чтобы найти положение элемента, который вы хотите переместить, O(log n) и, очевидно, вам нужно сделать это.
Если у вас уже есть должность по какой-то странной причине:
Почему худший ход не может быть меньше O(log n) в BST: учитывайте, когда пытаетесь переместить корень, и следующий элемент находится на высоте дерева (например, у правого ребенка есть левый ребенок с левым ребенком с левым ребенком с левым ребенком... до высоты дерева). Тебе нужно O(log n) найти его.
Почему худший ход не может быть меньше O(log n) в пропущенном списке: рассмотрим элемент, который существует в O(log n) списки и сопровождается элементом, который существует в O(log n) из этих списков (если это возможно, кажется, что из рисунка, мое понимание skip-списков является несколько базовым). Очевидно, вам придется поменять соответствующие элементы в O(log n) списки.
Если у вас уже есть позиция, может существовать эффективная упорядоченная структура, для которой это возможно, но, вероятно, не для какой-либо древовидной структуры (из-за приведенного выше аргумента), которые, насколько мне известно, являются большинством эффективных упорядоченных структур.