Поиск предков: различия между версиями

Перейти к навигации Перейти к поиску
Строка 63: Строка 63:




Нижние границы справедливы для мощной модели клеточного зонда и выполняются для рандомизированных алгоритмов. Когда S > n1+", оптимальный компромисс для коммуникативных игр совпадает с (1). Заметим, что случай S = n1+o(1) практически устраняется при сведении к коммуникационной сложности, поскольку сообщения Алисы зависят только от lg S. Таким образом, нет асимптотической разницы между S = O(n) и, скажем, S = O(n2).
Нижние границы справедливы для мощной модели клеточного зонда и выполняются для рандомизированных алгоритмов. Когда <math>S \ge n^{1 + \varepsilon}</math>, оптимальный компромисс для коммуникативных игр совпадает с (1). Заметим, что случай <math>S = n^{1 + o(1)}</math> практически устраняется при сведении к коммуникационной сложности, поскольку сообщения Алисы зависят только от lg S. Таким образом, нет асимптотической разницы между <math>S = O(n)</math> и, скажем, <math>S = O(n^2)</math>.




Строка 70: Строка 70:
Следующие алгоритмические техники дают оптимальный результат:
Следующие алгоритмические техники дают оптимальный результат:


• B-деревья обеспечивают время запроса O(logB n) при линейном объеме памяти.
'''B-деревья''' обеспечивают время запроса <math>O(log_B \; n)</math> при линейном объеме памяти.


• Деревья слияния, предложенные Фредманом и Уиллардом [10], дают время запроса O(logb n). В основе этого результата лежит узел слияния – структура, которая может выполнять поиск среди b" значений за постоянное время. Это достигается путем признания того, что только несколько бит каждого значения являются важными, и упаковки соответствующей информации обо всех значениях в одно слово.
'''Деревья слияния''', предложенные Фредманом и Уиллардом [10], дают время запроса <math>O(log_b \; n)</math>. В основе этого результата лежит ''узел слияния'' – структура, которая может выполнять поиск среди <math>b^{\varepsilon}</math> значений за постоянное время. Это достигается путем признания того, что только несколько бит каждого значения являются важными, и упаковки соответствующей информации обо всех значениях в одно слово.


• Поиск ван Эмде Боаса [ ] способен решить задачу за время O(lg£) путем бинарного поиска длины самого длинного общего префикса между запросом и значением в T. Начиная поиск с просмотра таблицы на основе первых lg n бит и заканчивая, когда достаточно места для хранения всех ответов, можно сократить время запроса до O(lg((£ - lg n)/a)).
'''Поиск ван Эмде Боаса''' [18] способен решить задачу за время <math>O(lg \; \ell)</math> путем бинарного поиска длины самого длинного общего префикса между запросом и значением в T. Начиная поиск с просмотра таблицы на основе первых lg n бит и заканчивая, когда достаточно места для хранения всех ответов, можно сократить время запроса до <math>O(lg((\ell - lg \; n)/a))</math>.


• Методика Бима и Фич [4] позволяет выполнять многоходовый поиск самого длинного общего префикса, поддерживая точный баланс между I и n. Это актуально, когда объем памяти составляет не менее n1+", и дает третью ветвь (1). Петрашку и Торуп [ ] показывают, как можно реализовать родственные идеи при меньшем объеме памяти, что дает последнюю ветвь (1).
'''Методика Бима и Фич''' [4] позволяет выполнять многоходовый поиск самого длинного общего префикса, поддерживая точный баланс между <math>\ell</math> и n. Это актуально, когда объем памяти составляет не менее <math>n^{1 + \varepsilon}</math>, и дает третью ветвь (1). Петрашку и Торуп [15] показывают, как можно реализовать родственные идеи при меньшем объеме памяти, что дает последнюю ветвь (1).




Заметим, что внешняя память участвует в достижении оптимального компромисса только за счет члена O(logB n), приходящегося на B-деревья. Таким образом, оптимальным является либо использование стандартных B-деревьев, основанных на сравнении, либо использование наилучшей стратегии пословной RAM-машины, полностью обходящейся без внешней памяти.
Заметим, что внешняя память участвует в достижении оптимального компромисса только за счет члена <math>O(log_B \; n)</math>, приходящегося на B-деревья. Таким образом, оптимальным является либо использование стандартных B-деревьев, основанных на сравнении, либо использование наилучшей стратегии пословной RAM-машины, полностью обходящейся без внешней памяти.




4551

правка

Навигация