4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 77: | Строка 77: | ||
Санковски также показал, как получить еще более быстрое время обновления O( | Санковски также показал, как получить еще более быстрое время обновления <math>O(n^{1,495}) \;</math> за счет увеличения времени выполнения запросов <math>O(n^{1,495}) \;</math>: | ||
Теорема 4 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы и операции вставки и удаления за время O( | '''Теорема 4 (Санковски [13], 2004). Пусть дан ориентированный граф общего вида с n вершинами. Существует рандомизированный алгоритм с односторонней ошибкой для решения полностью динамической задачи о транзитивном замыкании, поддерживающий запросы и операции вставки и удаления за время <math>O(n^{1,495}) \;</math>.''' | ||
Строка 86: | Строка 86: | ||
Теорема 5 (Родитти и Цвик 2002 [10]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O( | '''Теорема 5 (Родитти и Цвик 2002 [10]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время <math>O(m \sqrt{n})</math>, а запросы – за время <math>O(\sqrt{n})</math> в наихудшем случае.''' | ||
Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m+ n log n), а запросы – за время O(n) в наихудшем случае. | '''Теорема 6 (Родитти и Цвик 2004 [11]). Пусть дан ориентированный граф общего вида с n вершинами и m ребрами. Существует детерминированный алгоритм для решения полностью динамической задачи о транзитивном замыкании, поддерживающий операции вставки и удаления за амортизированное время O(m+ n log n), а запросы – за время O(n) в наихудшем случае.''' | ||
Заметим, что результаты теорем 5 и 6 являются субквадратичными для m = o( | Заметим, что результаты теорем 5 и 6 являются субквадратичными для <math>m = o(n^{1,5}) \;</math> и <math>m = o(n^2) \;</math>, соответственно. Более того, они не основываются на быстром перемножении матриц, которое является теоретически эффективным, но непрактичным. | ||
Строка 121: | Строка 121: | ||
Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения | Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения | ||
== Применение == | == Применение == |
правка