4

I know that there is std::set::lower_bound and the time complexity is O(log), and i see that std::lower_bound is much slower than std::set::lower_bound when operates on std::set.

I googled and found this:

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

so it's clear that because of the std::advance is linear for set::iterator, the whole std::lower_bound takes up to O(n).

However, it runs much faster than O(n) when i use it(and so did some friends say), can anybody explain why or tell me it's just not like that.

4

2 回答 2

1

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

问题是复杂性变化无常：O(N)什么？

非随机访问迭代器的复杂性保证是：

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

取决于迭代或比较是瓶颈，这实际上改变了一切！

理论上，在排序关联容器的情况下，人们可能希望专门std::lower_bound利用数据已经排序这一事实。但是在实践中它是相对困难的。主要问题是不set知道传递给的和的比较谓词lower_bound确实是相同的，因此算法需要假设情况并非如此（除非另有证明）。而且由于该算法采用迭代器而不是范围/容器，因此证明其他情况留给读者作为练习。

于 2013-08-11T11:02:11.890 回答
1

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

于 2013-08-11T09:52:01.970 回答