multiset、map 和 hash map 的复杂度

Question

我想了解在Big O符号表示法中，STL multiset、map和hash map类的复杂度情况，包括:

• 插入条目
• 访问条目
• 检索条目
• 比较条目

- Harry

---

这是我的帖子，我不明白为什么显示为不活跃状态，因此无法更改... - Harry

Answer 1

map、set、multimap 和 multiset

这些使用红黑树实现，是一种平衡二叉搜索树。它们具有以下渐进运行时间：

插入：O(log n)
查找：O(log n)
删除：O(log n)

hash_map、hash_set、hash_multimap 和 hash_multiset

这些使用哈希表实现。它们具有以下运行时间：

插入：期望为 O(1)，最坏情况为 O(n)
查找：期望为 O(1)，最坏情况为 O(n)
删除：期望为 O(1)，最坏情况为 O(n)

如果使用适当的哈希函数，则几乎不会看到最坏情况的行为，但这是需要记住的事情 - 例如，请参见 Crosby 和 Wallach 的 算法复杂度攻击拒绝服务 示例。

- Adam Rosenfield

---

你所说的hash_*是否都指的是C++11无序容器和Boost.Unordered容器？ - myWallJSON

hash_*类模板是Silicon Graphics STL的一部分。在C++11修订版中，它们以unordered_*名称（如unordered_map、unordered_set等）的形式被纳入其中。此外，它们也被包含在libstdc++、Visual C++和Boost C++库中。 - milpita

@CEOatApartico：修复了失效的链接。 - Adam Rosenfield

@PauliusLiekis 你不知道你在说什么。Big-O是根据定义的“上限”，与最坏情况、平均情况、最佳情况无关。 - ypnos

我认为这样做是有道理的。假设有一个适当的哈希函数和大小的哈希映射，您“期望”桶的大小不随n而增长，并获得平均情况下的O(1)。选择适当的哈希函数是开发人员的责任。为了保证适当的大小（负载因子），插入时可能会触发重新哈希，我们获得最坏情况下的O(n)+O(1)=O(n)。Landau符号不能涵盖两种不同算法之间的区别！因此，您所剩下的就是指定平均情况和最坏情况的两个不同度量，并且两者都可以使用O()、o()、Ө()等。 - ypnos

Answer 2

对于set、multiset、map、multimap，它们的时间复杂度为O(logn)，因为它们使用平衡二叉树来组织数据。

对于unordered_set和unordered_map，则使用哈希表来组织数据。因此，这些操作的时间复杂度为O(1)。这是在不需要按排序顺序处理数据时执行任何操作的完美方式。

- Aniket Babhulkar