Поиск предков: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 52: | Строка 52: | ||
(1) <math>min \begin{cases} | (1) <math>min \begin{cases} | ||
log_b \; n = \Theta(min \{ log_B \; n, log_{\ell} \; n \}) \\ | log_b \; n = \Theta(min \{ log_B \; n, log_{\ell} \; n \}) \\ | ||
\\ | |||
lg \frac{\ell - lg \; n}{a} \\ | 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(\frac{a}{lg \; n} \cdot lg \frac{\ell}{a})} \\ | ||
\frac{lg \frac{\ell}{a}}{lg} | \\ | ||
\frac{lg \frac{\ell}{a}}{lg(\frac{lg \frac{\ell}{a}}{lg \frac{lg \; n}{a}})} | |||
\end{cases}</math> | \end{cases}</math> | ||
Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время | Эта граница достигается детерминированным алгоритмом запроса. Для любого пространства S структура данных может быть построена за время O(S) с помощью рандомизированного алгоритма, начиная с множества T, заданного в отсортированном порядке. Обновления выполняются за ожидаемое время <math>t_q + O(S/n)</math>. Таким образом, помимо нахождения элемента за один запрос предка, обновления изменяют минимальную часть структуры данных. | ||