Временная сложность std :: lower_bound для отсортированного вектора
я учился std::upper_bound от http://www.cplusplus.com/reference/algorithm/upper_bound/
и я столкнулся с тем, что это может работать в линейном времени на неслучайный доступ итераторы.
Мне нужно использовать это для отсортированного вектора. Теперь я не знаю, каковы неслучайный доступ итераторы и будет ли это выполняться в логарифмическом времени на отсортированный вектор.
Может кто-нибудь прояснить это для меня.
Решение
§ 23.3.6.1 [vector.overview] / p1:
Вектор — это контейнер последовательности, который поддерживает итераторы произвольного доступа.
итератор произвольного доступа это тот, который может вычислить смещение произвольного элемента за постоянное время, без необходимости итерации из одного места в другое (что приведет к линейной сложности).
std::lower_bound сама обеспечивает общую реализацию алгоритма бинарного поиска, который не заботится о том, какой итератор используется для указания диапазонов (для этого требуется, чтобы итератор имел по крайней мере вперед категория). Он использует вспомогательные функции, такие как std::advance итеративно ограничивать диапазоны в своем бинарном поиске. С std::vector<T>::iterator который является категории произвольного доступа, std::lower_bound работает с логарифмической сложностью времени в отношении количества шагов, необходимых для итерации по элементам, так как он может разделить диапазон пополам на каждом шаге за постоянное время.
§ 25.4.3 [alg.binary.search] / p1:
Все алгоритмы в этом разделе являются версиями бинарного поиска и предполагают, что последовательность
искомый разделен относительно выражения, образованного связыванием ключа поиска с аргументом
подразумеваемая или явная функция сравнения. Они работают на итераторах с произвольным доступом, минимизируя
количество сравнений, которое будет логарифмическим для всех типов итераторов. Они особенно уместны
для итераторов с произвольным доступом, потому что эти алгоритмы делают логарифмическое число шагов по данным
состав. Для итераторов без произвольного доступа они выполняют линейное число шагов.
Другие решения