4817
правок
Нижняя граница для динамической связности: различия между версиями
Перейти к навигации
Перейти к поиску
м
Нижняя граница для динамической связности (посмотреть исходный код)
Версия от 11:28, 18 августа 2025
, 18 август→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
Чтобы полностью сформулировать задачу, будем считать, что элементы <math>A[i]</math> берутся из произвольной группы <math>G</math>, содержащей не менее <math>2^{\delta}</math> элементов. В модели клеточного зонда с b-битными ячейками обозначим за <math>t_u^{\Sigma}</math> сложность обновления (update), а за <math>t_q^{\Sigma}</math> – сложность проверки (testsum) (которая также является нижней границей sum). | Чтобы полностью сформулировать задачу, будем считать, что элементы <math>A[i]</math> берутся из произвольной группы <math>G</math>, содержащей не менее <math>2^{\delta}</math> элементов. В модели клеточного зонда с b-битными ячейками (клетками) обозначим за <math>t_u^{\Sigma}</math> сложность обновления (update), а за <math>t_q^{\Sigma}</math> – сложность проверки (testsum) (которая также является нижней границей sum). | ||