Сложность поиска по набору множеств (C ++)

Question

У меня есть наборы натуральных чисел std::set<set::<int> > X. Теперь мне дают набор std::set<int> V, и я хочу знать, происходит ли он в X. Очевидно, что это можно сделать, вызвав функцию find, поэтому X.find(V) != X.end() должен возвращать true, если V находится в X.

Мой вопрос касается сложности этой операции, т.е. если X содержит n наборов натуральных чисел, какова временная сложность X.find(V)?

Answer 1

Поиск в наборе - это O (log n) по количеству элементов, независимо от того, из каких элементов они состоят, даже от других наборов. Если элемент равен другой набор, все, что вам нужно, это предикат упорядочения (использование адреса объекта является безопасным по умолчанию). Тем не менее, поиск целого числа, вложенного в набор множеств, в общем случае будет O (m log n).

Answer 2

Предположим, что e наборов в X такое, что сумма размеров всех e наборов равна n, т. Е. |S1| + |S2| + ... + |Se| = n, тогда в худшем случае X.find(V) примет O(m*log(e)), где m - это размер V, т. Е. |V| = m. Как видите, он не зависит от n.

Почему? Таким образом, set в STL обычно реализуется как самобалансирующееся двоичное дерево поиска. Поэтому высота root всегда равна O(log(e)), где e - это общее количество элементов в дереве на данный момент. Теперь обратите внимание, что в нашем случае узлы дерева являются множествами. set по умолчанию использует оператор меньше чем < для сравнения с другими set того же типа, что занимает O(min(|S1|, |S2|)) время для сравнения.

Поэтому в худшем случае, если установлено V мы хотим найти это один из листьев X, и все узлы на ветке от root до V имеют размер >= |V|, тогда сравнение каждого узла займет O(|V|) времени, а поскольку O(log(e)) узлы в этой ветке, это займет у нас O(m*log(e)) времени.