比较两个无序集合的平等有多贵？

Question

给定两个std::sets,可以简单地同时迭代两个集合并比较元素,从而产生线性复杂性.这不适用于std::unordered_sets,因为元素可以按任何顺序存储.因此,如何昂贵的是a == b对std::unordered_set？

Answer 1

最坏的情况是O(n²).

但是无序集实际上是通过哈希来排序的.因此可以比较散列(如果失败,则集合不能相等),然后验证相同的散列(线性)是否具有相同的值(对于具有相同散列的不同值的O(n²)).

在最好的情况下,这是O(n).

通常,如果散列函数是"好"(不同的对象 - >总是不同的散列),则复杂性倾向于O(n),如果散列函数是"坏"(一切总是具有相同的散列值),则复杂性倾向于O(n²)

Answer 2

operator==和 的复杂度operator!=：

一般情况下的线性复杂度。N ²在最坏的情况下，其中 N 是容器的大小。

标准第 23.2.5 条第 11 点中的更多详细信息：

对于unordered_setand unordered_map，其复杂度operator==（即调用 的==运算符、调用value_type返回的谓词 key_equal()以及调用返回的散列器的次数hash_function()）N在平均情况下与 N ²成正比，在最坏情况下，其中N是a.size().