Какова сложность для std :: upper_bound и std :: lower_bound для Vector в C ++ STL? - PullRequest
Новая
       91

Какова сложность для std :: upper_bound и std :: lower_bound для Vector в C ++ STL?

0 голосов
/ 18 марта 2020

Я много искал, но не могу ничего найти о сложности функций.

Я знаю, что в случае std :: set это log (n), но я понятия не имею о векторе .

Я проходил реализацию самой длинной увеличивающейся подпоследовательности, используя векторы и 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();

}

1 Ответ

2 голосов
/ 18 марта 2020

С https://en.cppreference.com/w/cpp/algorithm/lower_bound:

Сложность

Количество выполненных сравнений - логарифмическое c на расстоянии между первым и последним (не более log 2 (последний - первый) + O (1) сравнений). Однако для не LegacyRandomAccessIterators число приращений итераторов является линейным.

Для итераторов с произвольным доступом (например, с std::vector) функции Bounds просто выполняют двоичный поиск.

Для итераторов без произвольного доступа (например, из std::list и std::set) функции по-прежнему выполняют бинарный поиск, но это требует дополнительных затрат, поскольку им приходится увеличивать итераторы по одному элементу за раз для перемещения между элементами.

...