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

Вы можете себе представить, как можно было бы оптимизировать специальные случаи до 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. Я имел в виду, что есть специальные оптимизации для особых случаев.

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

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

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

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