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

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

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

Определение

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

predecessor(x), который возвращает наибольший элемент в $S,$ меньший или равный $x$
successor(x), который возвращает наименьший элемент в $S,$ больший или равный $x$

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

insert(x), который добавляет $x$ в множество $S$
delete(x), который удаляет $x$ из множества $S$

Проблема обычно анализируется в трансдихотомической модели вычислений, такой как словесное ОЗУ .

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

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

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

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

Для задачи статического предшественника Михай Патрашку и Миккель Торуп показали следующую нижнюю оценку оптимального времени поиска в модели ячейки-зонда : ^{[ 7 ]} $O(1)\min \left\{{\begin{array}{l}\log _{w}n\\\lg {\frac {\ell -\lg n}{a}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left({\frac {a}{\lg n}}\,\cdot \,\lg {\frac {\ell }{a}}\right)}}\\{\frac {\lg {\frac {\ell }{a}}}{\lg \left(\lg {\frac {\ell }{a}}\right/\left.\lg {\frac {\lg n}{a}}\right)}}\end{array}}\right.$ где ОЗУ имеет разрядность $w$ , набор содержит $n$ целые числа $\ell$ бит каждый и представлен в ОЗУ с помощью $S$ слова пространства и определения $a=\lg {\frac {S}{n}}+\lg w$ .

В случае, когда $w=\ell =\gamma \lg n$ для $\gamma >1$ и $S=n\cdot \lg ^{O(1)}n$ , оптимальное время поиска $\Theta (\lg \ell )$ и дерево Ван Эмде Боаса достигает этой границы. ^{[ 7 ]}

См. также

Ссылки

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

[Beame-1] Перейти обратно: ^а ^б ^с Бим, Пол; Фич, Вера (август 2002 г.). «Оптимальные границы проблемы предшественника и связанных с ней проблем» . Журнал компьютерных и системных наук . 65 (1): 38–72. дои : 10.1006/jcss.2002.1822 . S2CID 1991980 .

[Rahman-2] Рахман, Наиля; Коул, Ричард; Раман, Раджив (17 августа 2001 г.). Оптимизированные структуры данных предшественников для внутренней памяти (PDF) . Международный семинар по алгоритмической разработке. стр. 67–78.

[Willard-3] Уиллард, Дэн (24 августа 1983 г.). «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ (n)». Письма об обработке информации . 17 (2): 81–84. дои : 10.1016/0020-0190(83)90075-3 .

[Fredman90-4] Фредман, Майкл ; Уиллард, Дэн (1990). «Прорыв через теоретический информационный барьер с помощью термоядерных деревьев». Симпозиум по теории вычислений : 1–7.

[5] Андерссон, Арне; Торуп, Миккель (2007), «Динамические упорядоченные множества с экспоненциальными деревьями поиска», Журнал ACM , 54 (3): A13, arXiv : cs/0210006 , doi : 10.1145/1236457.1236460 , MR 2314255 , S2CID 8175703 .

[6] Раман, Раджив (1996), «Очереди с приоритетами: маленькие, монотонные и трансдихотомические», Четвертый ежегодный европейский симпозиум по алгоритмам (ESA '96), Барселона, Испания, 25–27 сентября 1996 г. , Конспекты лекций по информатике, том . 1136, Берлин: Springer-Verlag, стр. 121–137, doi : 10.1007/3-540-61680-2_51 , ISBN. 978-3-540-61680-1 , МР 1469229 .

[Mihai-7] Перейти обратно: ^а ^б Патрашку, Михай; Торуп, Миккель (21 мая 2006 г.). «Компромисс во времени и пространстве для поиска предшественников». Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений . стр. 232–240. arXiv : cs/0603043 . дои : 10.1145/1132516.1132551 . ISBN 1595931341 . S2CID 1232 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]