4817
правок
Полностью динамическая связность: верхняя и нижняя границы: различия между версиями
Материал из WEGA
Полностью динамическая связность: верхняя и нижняя границы (посмотреть исходный код)
Версия от 15:42, 12 июля 2014
, 12 июля 2014→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 53: | Строка 53: | ||
Теорема 1. Динамический граф G с n вершинами может поддерживать вставку и удаление дуг за амортизированное время O( | '''Теорема 1. Динамический граф G с n вершинами может поддерживать вставку и удаление дуг за амортизированное время <math>O(log^2 \; n)</math> на одно обновление и отвечать на запросы о связности за время <math>O(log \; n/ log \; log \; n)</math> в наихудшем случае.''' | ||
Позднее Торуп [ ] предложил еще одну структуру данных, которая позволяет обеспечить несколько иные временные границы: | Позднее Торуп [18] предложил еще одну структуру данных, которая позволяет обеспечить несколько иные временные границы: | ||
Теорема 2. Динамический граф G с n вершинами может поддерживать вставку и удаление дуг за амортизированное время O(log n • ( | '''Теорема 2. Динамический граф G с n вершинами может поддерживать вставку и удаление дуг за амортизированное время <math>O(log \; n • (log \; log \; n)^3)</math> на одно обновление и отвечать на запросы о связности за время <math>O(log \; n/log \; log \; log \; n)</math>.''' | ||
| Строка 65: | Строка 65: | ||
Наилучшая известная нижняя граница для задачи динамической связности имеет место при использовании вычислительной модели битового зонда (bit-probe model); ее предложили Патраку и Тарнифа [ ]. Модель битового зонда представляет собой вариант модели клеточного зонда (cell-probe model) с однобитными клетками. В этой модели память организована в виде клеток, и алгоритм может производить чтение из клетки или запись в нее за константное время. Количество клеточных зондов рассматривается в качестве меры сложности. Формальное определение этой модели можно найти в [13]. | Наилучшая известная нижняя граница для задачи динамической связности имеет место при использовании вычислительной модели [[битовый зонд|битового зонда]] (bit-probe model); ее предложили Патраку и Тарнифа [16]. Модель битового зонда представляет собой вариант модели [[клеточный зонд|клеточного зонда]] (cell-probe model) с однобитными клетками. В этой модели память организована в виде клеток, и алгоритм может производить чтение из клетки или запись в нее за константное время. Количество клеточных зондов рассматривается в качестве меры сложности. Формальное определение этой модели можно найти в [13]. | ||
Теорема 3. Рассмотрим реализацию битового зонда для задачи динамической связности, в которой операции обновления выполняются за амортизированное время | Теорема 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> | ||
\\ | |||
