Каков наилучший алгоритм для объединения непересекающихся множеств?

Question

Допустим, есть два (непересекающихся) набора точек (декартово пространство). Какой алгоритм сложности сложностей наилучший для объединения двух наборов?

Answer 1

Поскольку координаты точки являются произвольными и между ними нет особой связи, я не рассматриваю эту проблему как конкретную геометрическую задачу.Это общая проблема эффективного слияния S1 и S2 в новый набор S.

Я знаю о двух вариантах:

1) Когда наборы хранятся в хеш-таблице (фактически хэш-набор), объединение принимает O (| S1 | + | S2 |) за среднее .

2) Если вы храните структуры в сбалансированном дерево поиска , вы можете достичь наихудшего времени O (| S1 | * Log (| S1 |)), предполагая, что | S1 |> | S2 |.

Answer 2

На самом деле, если множества находятся в сбалансированном дереве поиска, я думаю, вы можете сделать это в O (| S2 | (1 + log (| S1 | / | S2 |)), где | S1 |> = | S2 |. Это оптимально в худшем случае.