4551
правка
Поиск предков: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
Нижние границы справедливы для мощной модели клеточного зонда и выполняются для рандомизированных алгоритмов. Когда S > | Нижние границы справедливы для мощной модели клеточного зонда и выполняются для рандомизированных алгоритмов. Когда <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( | • '''B-деревья''' обеспечивают время запроса <math>O(log_B \; n)</math> при линейном объеме памяти. | ||
• Деревья слияния, предложенные Фредманом и Уиллардом [10], дают время запроса O( | • '''Деревья слияния''', предложенные Фредманом и Уиллардом [10], дают время запроса <math>O(log_b \; n)</math>. В основе этого результата лежит ''узел слияния'' – структура, которая может выполнять поиск среди <math>b^{\varepsilon}</math> значений за постоянное время. Это достигается путем признания того, что только несколько бит каждого значения являются важными, и упаковки соответствующей информации обо всех значениях в одно слово. | ||
• Поиск ван Эмде Боаса [ ] способен решить задачу за время O( | • '''Поиск ван Эмде Боаса''' [18] способен решить задачу за время <math>O(lg \; \ell)</math> путем бинарного поиска длины самого длинного общего префикса между запросом и значением в T. Начиная поиск с просмотра таблицы на основе первых lg n бит и заканчивая, когда достаточно места для хранения всех ответов, можно сократить время запроса до <math>O(lg((\ell - lg \; n)/a))</math>. | ||
• Методика Бима и Фич [4] позволяет выполнять многоходовый поиск самого длинного общего префикса, поддерживая точный баланс между | • '''Методика Бима и Фич''' [4] позволяет выполнять многоходовый поиск самого длинного общего префикса, поддерживая точный баланс между <math>\ell</math> и n. Это актуально, когда объем памяти составляет не менее <math>n^{1 + \varepsilon}</math>, и дает третью ветвь (1). Петрашку и Торуп [15] показывают, как можно реализовать родственные идеи при меньшем объеме памяти, что дает последнюю ветвь (1). | ||
Заметим, что внешняя память участвует в достижении оптимального компромисса только за счет члена O( | Заметим, что внешняя память участвует в достижении оптимального компромисса только за счет члена <math>O(log_B \; n)</math>, приходящегося на B-деревья. Таким образом, оптимальным является либо использование стандартных B-деревьев, основанных на сравнении, либо использование наилучшей стратегии пословной RAM-машины, полностью обходящейся без внешней памяти. | ||
