4551
правка
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
Строка 130: | Строка 130: | ||
| <math>O(n^{1,575}) \;</math> | | <math>O(n^{1,575}) \;</math> | ||
| <math>O(n^{0,575}) \;</math> | | <math>O(n^{0,575}) \;</math> | ||
| | | Деметреску, Итальяно [4] | ||
|- | |- | ||
| Граф общего вида | | Граф общего вида | ||
| Монте-Карло | | Монте-Карло | ||
| <math>O(n^{1,575}) \;</math> | | <math>O(n^{1,575}) \;</math> | ||
| | | <math>O(n^{0,575}) \;</math> | ||
| | | Санковски [13] | ||
|- | |- | ||
| Граф общего вида | | Граф общего вида | ||
| Монте-Карло | | Монте-Карло | ||
| <math>O(n^{ | | <math>O(n^{1,495}) \;</math> | ||
| | | <math>O(n^{1,495}) \;</math> | ||
| | | Санковски [13] | ||
|- | |- | ||
| Граф общего вида | | Граф общего вида | ||
| Детерминированный | | Детерминированный | ||
| <math>O(n | | <math>O(m \sqrt{n})</math> аморт. | ||
| <math>O(n | | <math>O(\sqrt{n)}</math> | ||
| | | Родитти, Цвик [10] | ||
|- | |- | ||
| Граф общего вида | | Граф общего вида | ||
| Детерминированный | | Детерминированный | ||
| | | O(m + n log n) аморт. | ||
| | | O(n) | ||
| | | Родитти, Цвик [11] | ||
|} | |} | ||
Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения | Таблица 1. Полностью динамический алгоритм транзитивного замыкания с неявным представлением решения |
правка