std::set中的std::lower_bound函数的时间复杂度是多少？

Question

我知道有 std::set::lower_bound，时间复杂度为O(log)，同时我注意到在操作 std::set 时，std::lower_bound 比 std::set::lower_bound 慢得多。

我在谷歌上搜到了这个：

http://zh.cppreference.com/w/cpp/algorithm/lower_bound http://zh.cppreference.com/w/cpp/iterator/advance

所以很明显，因为std::advance在set::iterator上是线性的，整个std::lower_bound最坏情况下的时间复杂度为O(n)。

但是当我使用它时（我的一些朋友也是如此），它运行得比O(n)快得多，有人能解释一下为什么吗，或者告诉我这不是真的。

- iloahz

Answer 1

std::lower_bound() 算法在非随机访问迭代器上的复杂度保证为O(n)。如果该算法检测到搜索是在有序的关联式容器中，则可能利用树结构实现更好的复杂度。但我不知道是否有任何实现这样做。

- Dietmar Kühl

---

根据25.4.3.1的lower_bound函数：复杂度为最多log2(last-first) + O(1)次比较。 - user2249683

@DieterLücking：复杂性总是很难定义... Dietmar Kühl在这里介绍了总体复杂性，而您则专门针对比较次数。因此，你们两个都是正确的：在最坏情况下，迭代次数是O(N)，比较次数是O(log2(N))。最终哪一个会主导运行时间取决于具体情况。 - Matthieu M.

@Dietmar Kühl "如果该算法检测到搜索在有序关联容器上，则可以利用它"，您确定吗？因为 https://en.cppreference.com/w/cpp/algorithm/lower_bound 告诉我们使用 std::set::lower_bound 用于 std::set 和 std::multiset::lower_bound 用于 std::multiset，这被称为“首选”方法 :) 所以 std::lower_bound 是否尝试猜测数据类型？ - Nusrat Nuriyev

Answer 2

TL;DR：每当容器提供与现有算法相同名称的方法时，这是因为内部实现更快（依赖于容器的属性），因此您应该直接使用它。

---

问题在于复杂度是善变的：O(N) 是什么意思？

非随机访问迭代器的复杂度保证如下：

- O(N) 次迭代 - O(log2(N)) 次比较

根据迭代或比较哪个是瓶颈，这实际上改变了一切！

理论上，在排序的关联容器的情况下，可以希望专门化 std::lower_bound 以利用数据已经排序的事实；然而，在实践中，这相对困难。主要问题是无法确定 set 的比较谓词和传递给 lower_bound 的比较谓词是否相同，因此算法需要假设它们不是相同的（除非被证明是相同的）。而且由于算法使用迭代器而不是范围/容器，证明相反的情况留给读者作为练习。

- Matthieu M.