c++ - 通过 std::set 迭代的复杂性

Question

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

Answer 1

迭代整个 std::set 的算法复杂度为 O(n)。但时间消耗比迭代 std::vector 大，因为 vector 使用单个内存块。

如果你想在 2 个迭代器 itBegin 和 itEnd 之间迭代，它也将是 O(n1)，但 n1 将类似于std::distance(itEnd, itBegin)，在第一种情况下小于n。当您已经有了迭代器时就是这种情况。

如果你想在迭代之前通过值找到那些位置(你在开始时没有迭代器) - 这变成了 O(log n) + O(n2) 这实际上是 O (登录 n)。假设，如果您想从值 123 迭代到末尾 - 这将是 O(log n) 以找到指向 123 和 O(n2) 进行迭代。