Какова оптимальная производительность для алгоритмов слияния множеств?
Предположим, упорядоченные множества, которые поддерживают O(n) итерацию и O(log n) доступ к отдельным элементам, какова теоретически оптимальная сложность для объединения, пересечения и разности множеств? Предположим, что выделенная структура может использоваться для наборов, если результат того же типа, что и входные данные.
Редактировать:
Пусть n будет размером большего набора, m размером меньшего набора и d размером симметричной разности.
Алгоритм описан в этой статье. Он работает в O(m * log (n / m)), который считается оптимальным. Алгоритм затем модифицируется в этой статье, чтобы он также стал O(d * log (n / d)).
Противоречие, что оптимальный алгоритм может быть улучшен? Я думаю, что нет, так как d является новым параметром, O(m*log(n/m)) все еще оптимально по отношению к n и m. Но это конец или как быстро это возможно?