Сложность STL max_element

Question

Итак, по ссылке здесь: http://www.cplusplus.com/reference/algorithm/max_element/, функция max_element - это O (n), по-видимому, для всех контейнеров STL.Это правильно?Разве это не должно быть O (log n) для набора (реализованного в виде двоичного дерева)?

В некоторой связанной заметке я всегда использовал cplusplus.com для вопросов, на которые легче ответить, ноМне было бы любопытно, что другие думают о сайте.

Answer 1

Это линейно, потому что оно касается каждого элемента.

Бессмысленно даже использовать его на множестве или другом упорядоченном контейнере , используя тот же компаратор , потому что вы можете просто использовать .rbegin() в константевремя.

Если вы не используете одну и ту же функцию сравнения, нет гарантии, что ордера будут совпадать, поэтому, опять же, она должна касаться каждого элемента и должна быть как минимум линейной.

Хотя алгоритмы могут быть специализированными для разных категорий итераторов, нет способа специализировать их, основываясь на том, упорядочен ли диапазон итераторов.

Большинство алгоритмов работают с неупорядоченными диапазонами (включая max_element), для некоторых требуются диапазоныбыть заказанным (например, set_union, set_intersection), некоторые требуют других свойств для диапазона (например, push_heap, pop_heap).

Answer 2

Функция max_element равна O (n) для всех контейнеров STL.

Это неверно, потому что max_element применяется к итераторам, а не к контейнерам. Если вы дадите ему итераторы из набора, у него не будет возможности узнать, что они происходят из набора, и поэтому он будет проходить через все из них в поисках максимума. Итак, правильное предложение:

Функция max_element равна O (n) для всех прямых итераторов

Кроме того, если вы знаете, что управляете множеством, у вас уже есть доступ к методам, которые дают вам максимальный элемент быстрее, чем O (n), так зачем использовать max_element?

Answer 3

Алгоритмы STL не знают, из какого контейнера вы взяли итераторы, упорядочен ли он и какие ограничения порядка использовались. Это линейный алгоритм, который проверяет все элементы в диапазоне, отслеживая максимальное значение, видимое до сих пор.

Обратите внимание, что даже если вы можете использовать методы метапрограммирования для определения типа контейнера, в котором итераторы получены из этого, не гарантируется, что вы можете просто перейти к последнему элементу, чтобы получить максимум:

int values[] = { 1, 2, 3, 4, 5 };
std::set<int, greater<int> > the_set( values, values+5 );
std::max_element( the_set.begin(), the_set.end() ); //??

Даже если итераторы взяты из набора, это не последний, а первый элемент, который содержит максимум. С более сложными типами данных набор можно упорядочить с помощью другого ключа, который может не иметь отношения к минимальным / максимальным значениям.

Answer 4

Это алгоритм STL, поэтому он ничего не знает о контейнере.Так что этот линейный поиск - лучшее, что он может сделать для пары на прямых итераторах.