Несвязанные множества с реализацией леса без сжатия пути

Question

Рассмотрим лесную реализацию непересекающихся множеств только с эвристикой взвешенного объединения (БЕЗ СЖАТИЯ ПУТИ!) С n различными элементами. Определите T (n, m) как временную сложность наихудшего случая выполнения последовательности из n-1 объединений, и m находит в любом порядке, где m - любое положительное целое число, большее n.

Я определил T (n, m) как последовательность выполнения n-1 объединений, а затем m находит AFTERWARDS, потому что выполнение операции поиска на самом большом дереве займет самое длинное. Соответственно, T (n, m) = m * log (n) + n - 1, потому что каждое объединение принимает O (1), поэтому n-1 объединений составляет n-1 шагов, и каждая находка принимает log (n) шагов в качестве высота результирующего дерева после n-1 объединений ограничена log_2 (n).

Моя проблема в том, выглядит ли выбранный T (n, m) нормально?

Во-вторых, является ли T (n, m) Big Omega (m * log (n))? Я утверждаю, что это с c = 1 и n> = 2, учитывая, что наименьшее возможное T (n, m) составляет m * log (2) + 1, что, очевидно, больше, чем m * log (2). Кажется довольно глупым спрашивать об этом, но решение оказалось слишком легким, поэтому у меня есть подозрения относительно моей правильности.

Заранее спасибо.

Answer 1

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

Что касается доказательства того, что T (n, m) равно Ω (m log (n)), вам нужно показать, что существуют n ₀ и m ₀ и c такие что для всех n ≥ n ₀ и всех m ≥ m ₀ справедливо, что T (n, m) ≥ cm log (n). То, что вы написали, вероятно, показывает это только для n = 2.