Вычислительная сложность операций TreeSet в Java?
Я пытаюсь разрешить некоторые вещи относительно сложности в некоторых операциях TreeSet. На javadoc это говорит:
"Эта реализация обеспечивает гарантируемый журнал (n), время, стоившее за основные операции (добавьте, удалите, и содержит)".
Пока все хорошо. Мой вопрос - то, что происходит на addAll (), removeAll () и т.д. Здесь, javadoc для Набора говорит:
"Если указанный набор является также набором, addAll операция эффективно изменяет этот набор так, чтобы его значение было объединением двух множеств".
Это просто объясняет логический результат операции, или это дает подсказку о сложности? Я имею в виду, если бы два набора представлены, например, красно-черные деревья, было бы лучше так или иначе присоединиться к деревьям, чем "добавить" каждый элемент одного к другому.
В любом случае существует ли способ объединить два TreeSets в один с O (logn) сложность?
Заранее спасибо. :-)
4 ответа
Вы можете себе представить, как можно было бы оптимизировать частные случаи до 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 п). Поскольку документация не дает намеков на сложность, вы можете написать свой собственный алгоритм, если производительность для вас критична.
Невозможно выполнить слияние деревьев или наборов соединений, как в структурах данных с несвязанными наборами, потому что вы не знаете, являются ли элементы в двух деревьях непересекающимися. Поскольку структуры данных имеют сведения о содержимом в других деревьях, необходимо проверить, существует ли один элемент в другом дереве, прежде чем добавлять к нему или, по крайней мере, пытаться добавить его в другое дерево и отменить добавление, если вы найдете его на путь. Значит, это должно быть O (MlogN)