116
правок
Изменения
→Введение
Наша структура данных должна поддерживать следующие операции:
* <tex>\mathrm {Makeset(x)}</tex> {{---}} создать новое множество из <tex>1 </tex> элемента <tex>x </tex>. Время: <tex>O(1)</tex>* <tex>\mathrm {Union(A, B)}</tex> {{---}} объединить множества <tex>A </tex> и <tex>B </tex> в одно. Время: <tex> O(1) </tex>, без учета времени на операцию <tex>find\mathrm{Find}</tex>, которая используется, если множества <tex>A </tex> и <tex>B </tex> заданы своими произвольными представителями.
* <tex>\mathrm {Find(x)}</tex> {{---}} найти множество, в котором содержится элемент <tex> x </tex>. Время; <tex>O(\log {n})</tex> в худшем случае, <tex>O(\alpha(n))</tex> {{---}} в среднем (<tex>\alpha(n)</tex> {{---}} обратная функция Аккермана), где n {{---}} размер множества.
* <tex>\mathrm{Delete(x)}</tex> {{---}} удалить элемент x из содержащего его множества. Время: <tex>O(1)</tex>
В дальнейшем мы будем использовать следующие понятия и обозначения:
