$s.lower-bound常数小$
by ybw051114 @ 2018-08-23 12:49:17
lower_bound(s.begin(), s.end())的复杂度是O(n)的。。
by Rorshach @ 2018-08-23 12:54:06
官方对std::lower_bound的时间复杂度解释是：
>进行的比较次数与 first 和 last 间的距离成对数（至多 log
2(last - first) + O(1) 次比较）。然而，对于非随机访问迭代器 (RandomAccessIterator) ，迭代次自增次数为线性。
std::set只提供双向迭代器，所以你的一次查找时间复杂度退化为O(n)的。但是std::set的成员函数lower_bound时间复杂度是O(logn)的，所以不是常数，而是复杂度有问题。
by cosmicAC @ 2018-08-23 12:54:35