4446
правок
Поиск предков: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
Пусть S – количество слов доступной памяти. (В случае внешней памяти это эквивалентно S/B страниц). Определим <math>a = lg \; S \cdot \ell / n</math>. Также определим <math>lg \; x = \left \lceil log_2(x + 2) \right \rceil</math> таким образом, что <math>lg \; x \ge 1</math>, даже если <math>x \in [0, 1]</math>. Тогда оптимальное время поиска составляет, с точностью до константных коэффициентов: | Пусть S – количество слов доступной памяти. (В случае внешней памяти это эквивалентно S/B страниц). Определим <math>a = lg \; S \cdot \ell / n</math>. Также определим <math>lg \; x = \left \lceil log_2(x + 2) \right \rceil</math> таким образом, что <math>lg \; x \ge 1</math>, даже если <math>x \in [0, 1]</math>. Тогда оптимальное время поиска составляет, с точностью до константных коэффициентов: | ||
(1) <math>min \begin{cases} | |||
log_b \; n = \Theta(min \{ log_B \; n, log_{\ell} \; n \}) \\ | |||
lg \frac{\ell - lg \; n}{a} \\ | |||
\frac{lg \frac{\ell}{a}}{lg(\frac{a}{lg \; n} \cdot lg \frac{\ell}{a})} \\ | |||
\frac{lg \frac{\ell}{a}}{lg} | |||
\end{cases}</math> | |||
Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время tq + O(S/n). Таким образом, помимо нахождения элемента за один запрос предка, обновления изменяют минимальную часть структуры данных. | Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время tq + O(S/n). Таким образом, помимо нахождения элемента за один запрос предка, обновления изменяют минимальную часть структуры данных. | ||
