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：

Complexity

The number of comparisons performed is logarithmic in the distance between first and last (At most log₂(last - first) + O(1) comparisons). However, for non-LegacyRandomAccessIterators, the number of iterator increments is linear.

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

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

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

What is the complexity for std::upper_bound and std::lower_bound for Vector in C++?

c++

stdvector

lower-bound

upperbound

lis