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

Question

Я пытаюсь прояснить некоторые вещи, связанные с сложностью некоторых операций TreeSet. На Javadoc он говорит:

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

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

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

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

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

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

Answer 1

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

Edit:

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

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

Answer 2

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

Answer 3

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

EDIT - догадываюсь я прочитал код слишком быстро, TreeSet можно использовать только O (N) алгоритм, если это резервное карта пуста

Answer 4

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