一组搜索的复杂度（C ++）

Question

我有一组正整数std::set<set::<int> > X。现在，给我一个集合std::set<int> V，我想知道它是否出现在X中。显然，这可以通过调用功能find来完成，因此如果X.find(V) != X.end()位于V中，则X应该返回true。

我的问题是关于此运算的复杂性，即X包含n组正整数，X.find(V)的时间复杂度是多少？

我有一组正整数std :: set <:>>X。现在给了我一个std :: set V，我想知道它是否出现在X中。显然，可以做到这一点。通过调用...

Answer 1

在一个集合中搜索元素的数量为O（log n），无论元素由什么构成，甚至其他集合也是如此。如果元素is

的另一个集合，则只需要一个排序谓词（使用对象的地址是安全的默认值）。但是，搜索嵌套在一组集合中的整数通常将为O（m log n）。

Answer 2

[假设e中有X个集合，使得所有e个集合的大小之和为n，即|S1| + |S2| + ... + |Se| = n，那么在最坏的情况下，X.find(V)将取O(m*log(e))，其中[ C0]是m的大小，即V。如您所见，它独立于|V| = m。