std::set的erase操作复杂度异常？

Question

我试图弄清楚从std :: set中删除多个元素的复杂性。我正在使用这个页面作为参考。

它声称使用迭代器删除单个项目的复杂度是平摊O（1），但使用范围形式删除多个项目的复杂度是log（c.size（））+ std :: distance（first，last）（即集合大小的对数+删除的元素数）。

直接看，如果要删除的元素数量（n）远小于集合中的元素数量（m），这意味着循环遍历要删除的元素并逐个删除比一次性删除它们更快（O（n）），前提是n << m，则O（log m））。

显然，如果真的是这样，第二种形式的内部实现将执行上述循环。

这是站点上的错误吗？规格书上的错误吗？还是只有我错过了什么？

谢谢， 沙哈尔

- Shachar Shemesh

---

使用范围形式删除多个元素的时间复杂度为log(c.size()) + std::distance(first, last)，即集合大小的对数与删除元素数量的和。当集合大小固定时，删除的元素数量为n，则时间复杂度恰好为O(n)，这与逐个删除的时间复杂度相同。 - Cthulhu

有趣，我猜你可以两种方式测试一下，看看有什么区别。也许在每次单独删除后重置迭代器会有一些开销（因为我认为这会使迭代器无效）。 - Simon Bosley

@Cthulhu，当复杂度中使用加号时，同样的逻辑也适用。任何您认为是常数（甚至是有界的）的东西都自动具有O(1)的复杂度。 - Shachar Shemesh

Answer 1

集合中的元素内部以平衡二叉树存储。平衡树是一棵树，其中任意节点的左右子树的最大高度差为1。

保持平衡结构对于保证在树（集合）中搜索任何元素最坏情况下需要 O(log(n)) 步骤非常重要。

删除一个元素可能会破坏平衡。为了恢复平衡，必须执行旋转操作。在某些情况下，单个删除会导致多个旋转，因此该操作需要 O(log(n)) 步骤，但平均而言，删除需要 O(1) 步骤。

因此，当集合中散布着多个元素需要逐个删除时，摊销成本很高的概率将为每次删除 O(1)。

删除范围内的几个元素（first, last，其中一个元素跟随下一个元素）几乎肯定会破坏平衡，这会导致复杂度中的对数因子：log(n) + std::distance(first, last)

- Andrushenko Alexander

Answer 2

看起来问题隐藏在“摊销”这个词背后。单个项目的删除具有O(log(c.size()))的复杂度，但是摊销复杂度为O(1)。

在循环中执行多个单个删除操作将导致成本为log(c.size()) + 删除数量，这正是范围形式的复杂度。

沙哈尔

- Shachar Shemesh

---

“amortized” 不是一个虚词，它是一个广为接受的计算机科学术语：http://en.wikipedia.org/wiki/Amortized_analysis。 - R. Martinho Fernandes

好的，“weasel”这个词有点过分了。我认为删除严格的上限语句会导致混淆。如果你只提供操作的摊销复杂度，你往往会剥夺程序员知道该期望什么的能力。我同意仅使用O复杂度同样具有误导性（就像在这里一样），但我认为标准应该同时提到两者。 - Shachar Shemesh