Поскольку мы знаем, что набор реализован с использованием красно-черных деревьев, поэтому вставка элемента будет задачей сложности O (log N). Но если нам дан вектор из n различных целых чисел, поэтому создание набора из него должно выполняться задачей NlogN. Но во многих местах я обнаружил, что это дается как O (N). Может кто-нибудь, пожалуйста, помогите мне решить эту проблему. Заранее спасибо.
Ссылка на место, где я прочитал это Сложность построения набора из списка?
O(N) времени для сборки, если у вас есть все N элементы, которые легко доступны. Сет берет O(NlogN) несмотря ни на что. 27.07.2020 But in many places, I found it is given as O(N) Мы не можем рассказать вам о ситуациях, о которых мы не знаем. Пожалуйста, назовите (ссылку) эти многочисленные места (или хотя бы первое). Может быть, есть больше ограничений на ввод, который вы замалчиваете? 27.07.2020 O(N), мы бы получили алгоритм сортировки O(N). 27.07.2020 set определяется как операция O(log N), и красно-черное дерево может достичь этого. 27.07.2020 n * sum( i / 2^i ) from i = 1 ... logN, что меньше 2n и, следовательно, ограничено O(n). 27.07.2020 Если вектор уже отсортирован, то построение set действительно O(N) (но в общем случае нет!).
Из cppreference:
template< class InputIt >
set( InputIt first, InputIt last,
const Compare& comp = Compare(),
const Allocator& alloc = Allocator() );
Конструктор диапазона. Создает контейнер с содержимым диапазона [first, last). Если несколько элементов в диапазоне имеют ключи, которые сравниваются эквивалентными, не указано, какой элемент вставляется.
Сложность
N log(N), где N = std::distance(first, last) в общем случае линейно по N, если диапазон уже отсортирован с помощью value_comp().
Соответствующая цитата из стандарта:
22.4.6.2#4 Сложность: линейна по N, если диапазон [first ,последний) уже отсортирован с помощью comp и иначе NlogN, где N последний - первый.
Стандарт определяет только то, что контейнеры делают, а не то, как они это делают. Использование красно-черного дерева типично, но не обязательно для реализации std::set.
Amortized constant if the insertion happens in the position just before the hint, logarithmic in the size of the container otherwise.Я думаю, дело в том, что если карта уже содержит элементы, то вы не можете гарантировать, что вставка произойдет в позиции непосредственно перед подсказкой. Таким образом, одна вставка — это O(logN), а предположительно N вставок — это O(NlogN). 31.07.2020