通过 std::set 迭代的复杂性

Question

我知道迭代整个集合的时间复杂度需要O(n)时间，其中n集合的大小。问题是，两个迭代器 和 之间迭代的复杂度是itBegin多少itEnd？也许是这样的O(itEnd - itBegin + log n)，但我无法证明。

Answer 1

复杂度将为 o(n) （n 中的小 o），而不是 O(n)，这意味着在最坏的情况下您将迭代整个集合。