Вычислительная сложность операций TreeSet в Java?

Question

Я пытаюсь прояснить некоторые аспекты сложности некоторых операций TreeSet. На javadoc написано:

"Эта реализация обеспечивает гарантированная стоимость журнала (n) для основные операции (добавить, удалить и содержит). "

Пока все хорошо. Мой вопрос заключается в том, что происходит с addAll (), removeAll () и т. Д. Здесь Javadoc для Set говорит:

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

Это просто объясняет логический результат операции или дает намек на сложность? Я имею в виду, если два набора представлены, например, красно-черные деревья было бы лучше как-то соединить деревья, чем "добавлять" каждый элемент одного в другой.

В любом случае, есть ли способ объединить два TreeSets в один со сложностью O (logn)?

Заранее спасибо. : -)

Answer 1

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

Редактировать:

http://net.pku.edu.cn/~course/cs101/resource/Intro2Algorithm/book6/chap14.htm

Описывает алгоритм особого случая, который может объединять деревья в O(log(m + n)), но обратите внимание на ограничение: все члены S1 должны быть меньше всехчлены S2.Это то, что я имел в виду, что есть специальные оптимизации для особых случаев.

Answer 2

Глядя на исходный код Java для TreeSet, похоже, что если переданная коллекция является SortedSet, то используется алгоритм времени O (n). В противном случае он вызывает super.addAll, который, как я предполагаю, приведет к O (n logn).

РЕДАКТИРОВАТЬ - думаю, я читаю код слишком быстро, TreeSet может использовать алгоритм O (n), только если его резервная карта пуста

Answer 3

Согласно этому сообщению в блоге:
http://rgrig.blogspot.com/2008/06/java-api-complexity-guarantees.html
это O (n log n). Поскольку в документации нет подсказок о сложности, вы можете написать свой собственный алгоритм, если производительность критична для вас.

Answer 4

Невозможно выполнить объединение деревьев или объединить наборы, как в структурах данных с несвязным набором, потому что вы не знаете, являются ли элементы в 2 деревьях непересекающимися.Поскольку структуры данных знают о содержимом в других деревьях, необходимо проверить, существует ли один элемент в другом дереве, прежде чем добавлять к нему или, по крайней мере, пытаться добавить его в другое дерево, и отменить его добавление, если вы найдете его впуть.Итак, должно быть O (MlogN) * ​​1001 *