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

Перейти к навигации Перейти к поиску
Строка 45: Строка 45:


== Основные результаты ==
== Основные результаты ==
Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили совпадающие верхние и нижние границы для статической задачи в моделях пословной RAM-машины, клеточного зонда, внешней памяти и коммуникативной игры.
Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили соответствующие верхние и нижние границы для статической задачи в моделях пословной RAM-машины, клеточного зонда, внешней памяти и коммуникативной игры.




Пусть S – количество слов доступной памяти. (В случае внешней памяти это эквивалентно S/B страниц). Определим a = lgS • tin. Также определим lgx = dlog2(x + 2)e таким образом, что lgx > 1, даже если if x 2 [0;1]. Тогда оптимальное время поиска составляет, с точностью до константных коэффициентов:
Пусть 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>. Тогда оптимальное время поиска составляет, с точностью до константных коэффициентов:




Источник — http://pco.iis.nsk.su/wega/index.php/Поиск_предков