c++ - 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 ₂ (last - first) + O(1)比较）。但是，对于非 LegacyRandomAccessIterators，迭代器增量的数量是线性的。

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

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