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

Полный результат Петрашку и Торупа [ ] представляет собой компромисс (1). Первоначально он был показан только для детерминированных алгоритмов запросов, но со временем был распространен и на нижнюю границу рандомизированного алгоритма [16]. Среди удивительных последствий этого результата было то, что классический поиск ван Эмде Боаса является оптимальным для почти линейного объема памяти (и, следовательно, для динамических структур данных), тогда как при наличии квадратичного объема памяти он может уступать технике Бима и Фич.

С технической точки зрения идея [ ] заключается в одновременном анализе нескольких запросов. Затем рассматривается коммуникативная игра, включающая все запросы, и доказывается версия леммы об исключении раунда с прямой суммой. Возможно, доказательство в данном случае даже проще, чем у обычной леммы об исключении раунда. Это достигается за счет рассмотрения более сильной модели индуктивного анализа, в которой алгоритму разрешается ''отклонить'' большую часть запросов, прежде чем приступить к зондированию.

Поскольку блоки размером wO(1) могут обрабатываться деревьями слияния за константное время, из этого следует, что коэффициенты w объема памяти не имеют значения. Более экстремальное применение этой идеи дают экспоненциальные деревья [ ]. Здесь блоки имеют размер @(n1~y), где у – достаточно небольшая константа. Блоки обрабатываются рекурсивно таким же образом, что дает в итоге O(lglg n) уровней. Если начальное время запроса не меньше tq > lg" n, то время запроса на каждом уровне уменьшается в геометрической прогрессии, так что общее время растет только на постоянный коэффициент. Однако при соответствующем выборе у любое полиномиальное требование к памяти сводится к линейному. Кроме того, экспоненциальное дерево может быть обновлено за время O(tq), даже если исходная структура данных была статической.