4817
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 15:43, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 70: | Строка 70: | ||
Теорема 3. Рассмотрим реализацию битового зонда для задачи динамической связности, в которой операции обновления выполняются за ожидаемое амортизированное время <math>t_u</math>, а запросы – за ожидаемое время <math>t_q</math>. Тогда для среднего случая распределения входных данных <math>t_u = \Omega (log^2 \; n/ log^2 \; (t_u + t_q))</math>. В частности, | Теорема 3. Рассмотрим реализацию битового зонда для задачи динамической связности, в которой операции обновления выполняются за ожидаемое амортизированное время <math>t_u</math>, а запросы – за ожидаемое время <math>t_q</math>. Тогда для среднего случая распределения входных данных <math>t_u = \Omega (log^2 \; n/ log^2 \; (t_u + t_q))</math>. В частности, | ||
<math>max \{ t_u, t_q \} = \Omega ((\frac{log \; n}{log \; log \; n})^2) \; </math> | <math>max \{ t_u, t_q \} = \Omega \left ( \left ( \frac{log \; n}{log \; log \; n} \right ) ^2 \right ) \; </math> | ||
