我知道遍历整个集合的时间复杂度需要
O(n) 时间，其中 n 是集合的大小。
问题是，在两个迭代器 itBegin 和 itEnd 之间进行遍历的复杂度是什么？可能类似于 O(itEnd - itBegin + log n)，但我无法证明。2个回答
0
整个 std::set 的迭代算法复杂度为 O(n)。但是时间消耗比迭代 std::vector 更大，因为 vector 使用单一内存块。
如果你想在两个迭代器 itBegin 和 itEnd 之间进行迭代，它的复杂度也是 O(n1)，但是 n1 将会是类似于 std::distance(itEnd, itBegin) 这样的值，这个值比第一个情况下的 n 要小。这种情况是当你已经有了迭代器时。
如果你想在迭代之前通过值来查找这些位置（在开始时没有迭代器），这将变成 O(log n) + O(n2)，实际上是 O(log n)。例如，如果你想从值 123 开始迭代到结尾，这将是 O(log n) 来查找到 123 的迭代器，然后是 O(n2) 来迭代。
- Galimov Albert
5
1"
O(log n) + O(n) 其实是 O(log n)" - 如果使用不同的字母表示集合大小和距离会更清晰（我将使用 n 和 d），但是这个断言本身就是错误的：假设 itBegin 是 begin()，itEnd() 是 end() - O(d) 占主导地位而不是 O(log n)，而对于附近的 itBegin/itEnd，O(log n) 占主导地位：除非有理由认为迭代器将始终接近，否则 O(n) 是更有意义的总体评估。 - Tony Delroy@TonyD，我认为你在这部分的断言是错误的：“say itBegin is begin() and itEnd() is end() - O(d) dominates O(log n)”。要获取begin()和end()，std::set不需要搜索任何内容，因此它们是O(1)。然后，在它们之间进行迭代类似于“for(; itBegin!=itEnd; ++itBegin)”这样的操作，其时间复杂度为O(n)。因此，总体时间复杂度为O(n)。 - Galimov Albert
你没有注意到我说过我会使用d来表示集合中迭代器之间的距离...在begin->end的情况下，d == n，所以“O(d) dominates O(log n)”与你的分析一致，它总体上是O(n)。既然你同意O(n)，那么更新一下你的答案怎么样？关于O(1) vs O(log n)——如果你从迭代器开始，你所说的是正确的，但是如果你只是搜索一个接近这些极端值或者在这些极端值处的元素，那么它将是更一般的O(log n)情况。 - Tony Delroy
@TonyD编辑了帖子以澄清
n的不同大小。但是，我应该提到在算法复杂度方面，O(n1)和O(n)之间没有区别，因为它们讨论的是复杂度，而不是墙上时钟时间消耗。 - Galimov Albert“O(n1)”和“O(n)”之间没有区别，这取决于正在解决的特定问题是否更加约束了“n1”。例如，如果您有一个任意大的“n”，但任务是搜索一个值并且需要取前后100个值来形成平均值，则在获取迭代器时它将被O(log n)支配，而常数节点迭代为O(1)并被忽略。总之，我认为正确的答案应该像“变成
O(log n)和O(n1)中更糟糕的那个”一样，最坏情况下为O(n)。另外，不确定“n2”从哪里来的...？ - Tony Delroy-2
复杂度将是o(n)（小o n），而不是O(n)，这意味着在最坏的情况下，您将遍历整个集合。
- Anis Belaid
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
itEnd = itBegin + 1，那么复杂度将是O(log n)而不是O(1)。 - OneOnen=1的情况。itBegin不是s.begin()，而itEnd也不是s.end()。 - OneOneO(itEnd - itBegin)。如果您知道itEnd - itBegin平均线性相关于n，则可以将其简化为O(n)。MikeMB所说的是"O(n)，其中n是迭代器之间的距离" - 即itEnd - itBegin。对于您的反例itEnd = itBegin + 1- 在C++中，将1添加到迭代器意味着下一个元素：它们相隔1个位置，并且使用MikeMB的定义n作为"迭代器之间的距离"，正如我所说的那样，这确实是n=1的情况。 - Tony Delroy