什么是启发式合并
启发式合并, 就是把n个大小为1的集合合并为一个大小为n的集合的一种方法. 其复杂度为(O(nlog n))
这种方法被广泛应用在各种毒瘤数据结构(树套树)中.....
当然, 集合合并操作的顺序是给定的(可以理解为强制在线)....(否则不就是(O(n))了吗)...
启发式合并方法
启发式合并的算法很简单, 就是当要合并两个集合 (s1, s2)时, 将大小较小的合并至大小较大的
//伪代码
if(|s1| < |s2|)
for all x in s1: s2.insert(x);
clear(s1);
else
for all x in s2: s1.insert(x);
clear(s2);
复杂度分析
为啥这个优化有这么好的效果呢?
复杂度证明: 考虑贡献法.
一个元素从一个集合被加入另一个集合时, 所在集合的规模至少扩大一倍. 如果没有分离操作且元素数目有限, 合并的次数是O(log n)的.
因为有n个元素, 所以复杂度O(n log n)
将其复杂度式写为 (T(n) = max_{kin[1, n]}(T(k)+T(n-k)+min(k, n-k) ))
通过以上证明, 所有类似这样的递归式, 其解都是 (O(nlog n))