algorithm - 不带路径压缩的森林实现的不相交集

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) ≥ c m log(n)。您所写的内容可以说仅针对 n = 2 显示了这一点。