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)次比较）。然而，对于非 LegacyRandomAccessIterators，迭代器增量的数量是线性的。

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

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