Проблема предшественника - Predecessor problem - Wikipedia

В Информатика, то проблема предшественника включает поддержание набор элементов в, учитывая элемент, эффективно запрос какой элемент предшествует или следует за этим элементом в порядке. Структуры данных используется для решения проблемы, включая сбалансированные бинарные деревья поиска, деревья ван Эмде Боаса, и деревья слияния. в статическая проблема предшественника, набор элементов не меняется, но в проблема динамического предшественника, вставки в набор и удаления из него разрешены.^[1]

Проблема предшественника - это простой случай ближайший сосед проблема, и структуры данных, которые ее решают, имеют приложения в таких проблемах, как целочисленная сортировка.

Определение

Проблема состоит в поддержании набора S, который содержит подмножество U целые числа. Каждый из них целые числа может храниться с размер слова из ш, подразумевая, что ${\displaystyle U\leq 2^{w}}$. Структуры данных, которые решают проблему, поддерживают следующие операции:^[2]

• предшественник (х), который возвращает самый большой элемент в S меньше или равно Икс
• преемник (х), который возвращает наименьший элемент в S больше или равно Икс

Кроме того, структуры данных, которые решают динамичный Версия проблемы также поддерживает следующие операции:

• вставить (х), что добавляет Икс к набору S
• удалить (х), который удаляет Икс из набора S

Проблема обычно анализируется в трансдихотомический модель вычисления Такие как слово RAM.

Структуры данных

X-быстрое дерево, содержащее целые числа 1 (001₂), 4 (100₂) и 5 ​​(101₂), который может быть использован для эффективного решения проблемы предшественника.

Одно простое решение этой проблемы - использовать сбалансированное двоичное дерево поиска, который достигает (в Обозначение Big O ) а Продолжительность из ${\displaystyle O(\log n)}$ для запросов предшественников. В Дерево Ван Эмде Боаса достигает времени запроса ${\displaystyle O(\log \log U)}$, но требует ${\displaystyle O(U)}$ Космос.^[1] Дэн Уиллард предложили улучшение использования этого пространства с помощью x-fast trie, что требует ${\displaystyle O(n\log U)}$ пространство и то же время запроса, и более сложный y-fast trie, что требует только ${\displaystyle O(n)}$ Космос.^[3] Деревья слияния, представлен Майкл Фредман и Уиллард, добейтесь ${\displaystyle O(\log _{w}n)}$ время запроса и ${\displaystyle O(n)}$ для запросов предшественников для статической задачи.^[4] Динамическая задача решена с использованием экспоненциальные деревья с ${\displaystyle O(\log _{w}n+\log \log n)}$ время запроса,^[5] и с ожидаемое время ${\displaystyle O(\log _{w}n)}$ с помощью хеширование.^[6]

Математические свойства

Было предпринято несколько попыток доказать нижняя граница по проблеме предшественника, или узнайте, какое время работы асимптотически оптимальный решения были бы. Например, Майкл Бим и Вера Эллен доказал, что для всех ценности ш, Существует ценность п со временем запроса (в Обозначение Big Theta ) ${\displaystyle \Omega \left({\tfrac {\log w}{\log \log w}}\right)}$, и аналогично для всех значений п, существует значение п так что время запроса ${\displaystyle \Omega \left({\sqrt {\tfrac {\log n}{\log \log n}}}\right)}$.^[1] Другие доказательства оценок снизу включают понятие сложность коммуникации.

Смотрите также

• Целочисленная сортировка
• y-fast trie
• Дерево слияния

Рекомендации

1. Бим, Пол; Фич, Вера (Август 2002 г.). «Оптимальные границы для проблемы предшественника и связанных проблем» (PDF). Журнал компьютерных и системных наук. 65 (1): 38–72. Дои:10.1006 / jcss.2002.1822.
2. Рахман, Наиля; Коул, Ричард; Раман, Раджив (17 августа 2001 г.). Оптимизированные структуры данных предшественников для внутренней памяти (PDF). Международный семинар по разработке алгоритмов. С. 67–78.
3. Уиллард, Дэн (24 августа 1983 г.). «Логарифмические запросы диапазона наихудшего случая возможны в пространстве space (n)». Письма об обработке информации. 17 (2): 81–84. Дои:10.1016/0020-0190(83)90075-3.
4. Фредман, Майкл; Уиллард, Дэн (1990). «Взрыв теоретического информационного барьера с помощью деревьев слияния». Симпозиум по теории вычислений: 1–7.
5. Андерссон, Арне; Торуп, Миккель (2007), «Динамические упорядоченные множества с экспоненциальными деревьями поиска», Журнал ACM, 54 (3): A13, arXiv:cs / 0210006, Дои:10.1145/1236457.1236460, МИСТЕР  2314255.
6. Раман, Раджив (1996), «Приоритетные очереди: маленькие, монотонные и трансдихотомические», Четвертый ежегодный европейский симпозиум по алгоритмам (ESA '96), Барселона, Испания, 25–27 сентября 1996 г., Конспект лекций по информатике, 1136, Берлин: Springer-Verlag, стр. 121–137, Дои:10.1007/3-540-61680-2_51, ISBN  978-3-540-61680-1, МИСТЕР  1469229.