std::set стереть аномалию сложности?

Я пытаюсь понять сложность удаления нескольких элементов из std::set. Я использую эту страницу в качестве источника.

В нем утверждается, что сложность удаления одного элемента с помощью итератора амортизируется O (1), но стирание нескольких элементов с использованием формы диапазона составляет log (c.size ()) + std::distance (first, last) (т.е. - log размера набора + количество удаленных элементов).

На первый взгляд, если количество стираемых элементов (n) намного меньше, чем количество элементов в наборе (m), это означает, что перебор стираемых элементов и стирание их по одному выполняется быстрее. (O(n)), чем стирание их одним вызовом (O(log m), предполагая n‹‹m).

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

Это ошибка на сайте? Ошибка в спецификациях? Я просто что-то упустил?

Спасибо, Шахар


c++ time-complexity stl stdset
person Shachar Shemesh    schedule 03.03.2014    source источник
comment
удаление нескольких элементов с использованием формы диапазона: log(c.size()) + std::distance(first, last) (т.е. - log размера набора + количество удаленных элементов). - с фиксированным размером набора масштабируется точно так же, как O (n), где n - количество удаленных элементов, что вы получаете, удаляя их один за другим.   -  person Cthulhu    schedule 03.03.2014
comment
Это интересно, я думаю, вы могли бы проверить это в обоих направлениях, чтобы увидеть разницу. Возможно, будут некоторые накладные расходы при сбросе итератора после каждого отдельного стирания (поскольку я думаю, что это делает итератор недействительным)   -  person Simon Bosley    schedule 03.03.2014
comment
@Cthulhu, та же логика применяется всякий раз, когда в сложности используется плюс. Все, что вы считаете постоянным (или даже ограниченным), автоматически имеет сложность O (1).   -  person Shachar Shemesh    schedule 03.03.2014

Ответы (2)


arrow_upward
2
arrow_downward

Кажется, проблема скрывается за (несколько ласковым) словом «амортизированный». Стирание одного элемента имеет сложность O log(c.size()), но амортизированную сложность O(1).

Таким образом, выполнение нескольких одиночных стираний в цикле будет стоить log(c.size()) + количество стираний, что точно соответствует сложности формы диапазона.

Шахар

person Shachar Shemesh    schedule 03.03.2014
comment
амортизированный не ласковое слово. Это устоявшийся термин в области информатики: en.wikipedia.org/wiki/Amortized_analysis. - person R. Martinho Fernandes; 03.03.2014
comment
Ладно, ласка немного жестковата. Я действительно думаю, что отказ от утверждения о строгой верхней границе приводит к путанице. Если вы предоставляете только амортизированную сложность операции, вы часто лишаете программиста возможности знать, чего ожидать. Я согласен с тем, что использование ТОЛЬКО сложности O может в равной степени вводить в заблуждение (как здесь), но я действительно думаю, что стандарт должен был упомянуть оба. - person Shachar Shemesh; 03.03.2014

arrow_upward
2
arrow_downward

Внутренне элементы набора хранятся в сбалансированном двоичном дереве. Сбалансированное дерево — это дерево, в котором максимальная разница высот между левым и правым поддеревьями любого узла равна 1.

Поддержание сбалансированной структуры важно для гарантии того, что поиск любого элемента в дереве (в наборе) занимает в худшем случае O(log(n)) шагов.

Удаление элемента может нарушить баланс. Для восстановления баланса необходимо выполнять вращения. В некоторых случаях одно удаление вызывает несколько поворотов, так что операция занимает O(log(n)) шагов, но в среднем удаление занимает O(1) шагов.

Так, когда несколько элементов, разбросанных по набору, необходимо удалить один за другим, амортизированная стоимость с высокой вероятностью составит O(1) за удаление.

Удаление нескольких элементов в диапазоне (first, last, где один элемент следует за другим) почти наверняка нарушит баланс, что приводит к логарифмическому коэффициенту сложности: log(n) + std::distance(first, last)

person Andrushenko Alexander    schedule 11.01.2019