4551
правка
Поиск предков: различия между версиями
Материал из WEGA
м
→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 126: | Строка 126: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Подход к реализации деревьев слияния с инструкциями AC0 известен [2], но для других стратегий запросов это не так. Каков наилучший компромисс между запросами, достижимый для RAM-машины | Подход к реализации деревьев слияния с инструкциями AC0 известен [2], но для других стратегий запросов это не так. Каков наилучший компромисс между запросами, достижимый для RAM-машины <math>AC^0</math>? В частности, может ли поиск ван Эмде Боаса быть реализован с помощью инструкций <math>AC^0</math>? | ||
Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить | Можно ли сделать время обновления детерминированным при решении динамической задачи? В частности, можно ли реализовать поиск ван Эмде Боаса с быстрым детерминированным обновлением? Это очень интересная задача, находящая применение в детерминированных словарях [ ]. Кроме того, можно ли детерминированным образом обновлять узлы слияния за константное время? Атомарные кучи [11] достигают этого результата при поиске только среди <math>(lg \; n)^{\varepsilon}</math> элементов, а не <math>b^{\varepsilon}</math>. | ||
Наконец, требуется ли запрос для обновления структуры предков? Иными словами, можно ли получить <math>t+u = o(t_q)</math>, сохранив при этом эффективное время запроса? | |||
== См. также == | == См. также == | ||
