C++中Vector的std::upper_bound和std::lower_bound的复杂性是多少

Question

std::lower_bound和std::upper_bound函数的复杂性是多少。

我知道在std::set<int>的情况下是log(n)，但我不知道std::vector<int>。

我正在使用向量和std::lower_bound实现最长递增子序列。

这个代码的复杂性是什么？

int LIS2(vector<int> a) {
vector<int> v;
for (int i = 0; i < a.size(); i++) {
auto it = lower_bound(v.begin(), v.end(), a[i]);
if (it != v.end()) 
*it = a[i];
else 
v.push_back(a[i]);
}
return v.size();
}

Answer 1

来源https://en.cppreference.com/w/cpp/algorithm/lower_bound:

复杂度

执行的比较次数是第一次和最后一次之间距离的对数(最多log₂(最后一次-第一次(+O(1(比较(。但是，对于非LegacyRandomAccessIterator，迭代器增量的数量是线性的。

对于随机访问迭代器(例如来自std::vector(，边界函数只是执行二进制搜索。

对于非随机访问迭代器(例如，来自std::list和std::set(，函数仍然执行二进制搜索，但存在额外的成本，因为它们必须一次增加迭代器一个元素以在元素之间移动。