不相交集，具有森林实现，无需路径压缩
考虑不相交集的森林实现，仅使用带有 n 个不同元素的加权并集启发式（无路径压缩！）。将 T(n,m) 定义为执行 n-1 并集序列的最坏情况时间复杂度，并且 m 以任意顺序查找，其中 m 是大于 n 的任何正整数。
我将 T(n,m) 定义为进行 n-1 并集的序列，然后进行 m 查找，因为在可能的最大树上进行查找操作将花费最长的时间。因此，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)。问这个问题似乎很愚蠢，但解决方案似乎太容易了，所以我怀疑我的正确性。
提前致谢。
Consider a forest implementation of disjoint sets with only the weighted union heuristics (NO PATH COMPRESSION!) with n distinct elements. Define T(n,m) to be the worst case time complexity of executing a sequence of n-1 unions and m finds in any order, where m is any positive integer greater than n.
I defined T(n,m) to be the sequence of doing n-1 unions and then m finds AFTERWARDS because doing the find operation on the biggest tree possible would take the longest. Accordingly, T(n,m) = m*log(n) + n - 1 because each union takes O(1) so n-1 unions is n-1 steps, and each find takes log(n) steps per as the height of the resultant tree after n-1 unions is bounded by log_2 (n).
My problem now is, does the T(n,m) chosen look fine?
Secondly, is T(n,m) Big Omega (m*log(n)) ? My claim is that it is with c = 1 and n >= 2, given that the smallest possible T(n,m) is m*log(2) + 1, which is obviously greater than m*log(2). Seems rather stupid to ask this but it seemed rather too easy for a solution, so I have my suspicions regarding my correctness.
Thanks in advance.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
是的，T(n, m) 看起来不错，但我想你可以给出一个正式的归纳证明，证明最坏的情况是并集后跟发现。
至于证明 T(n, m) 是 Ω(m log(n))，需要证明存在 n0 和 m0 和 c，使得对于所有 n ≥ n0 和所有 m ≥ m0，它认为 T(n, m) ≥ cm log(n)。您所写的内容可以说仅适用于 n = 2。
Yes to T(n, m) looking fine, though I suppose you could give a formal induction proof that the worst-case is unions followed by finds.
As for proving that T(n, m) is Ω(m log(n)), you need to show that there exist n0 and m0 and c such that for all n ≥ n0 and all m ≥ m0, it holds that T(n, m) ≥ c m log(n). What you've written arguably shows this only for n = 2.