4551
правка
Поиск предков: различия между версиями
Материал из WEGA
м
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 45: | Строка 45: | ||
== Основные результаты == | == Основные результаты == | ||
Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили | Основываясь на длительной серии исследований, Петрашку и Торуп [15,16] в конечном итоге получили соответствующие верхние и нижние границы для статической задачи в моделях пословной RAM-машины, клеточного зонда, внешней памяти и коммуникативной игры. | ||
Пусть S – количество слов доступной памяти. (В случае внешней памяти это эквивалентно S/B страниц). Определим a = | Пусть 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>. Тогда оптимальное время поиска составляет, с точностью до константных коэффициентов: | ||
