1、简单不相交集的合并算法本节的假定前提:1、 为算法书写方便起见，设任一集合都是1,2,n的子集 ；2、任意两个被合并的集合都是不相交的；3、集合上的运算只有 Union 和 Find。Union(I,J,K)：把名为 I 与 J 的集合进行合并，合并后的集合名为 K。初始共有 n 个单元素集，故 Union 最多可执行 n-1 次即 O(n)。Find(a)：给出 a 所在的集合名（算法中大多用数字表示集合名） 。此类问题中 Find 指令的执行通常也有 O(n)次，故一般讨论执行 O(n)条 Union 和 Find 指令所需要的时间。可以用来表示集合的数据结构很多，用什么样的算法和结构才能
2、使得完成上述任务的时间最少?Union(I,J,K) 算法中的数组说明：为加快处理速度，每个集合给予一个内部名和一个外部名。内部名与外部名 11 对应。例如：外部名 1 2 3集合 1,3,5,7 2,4,8 6内部名 2 3 1算法涉及 6 个数组，4 个与集合相关，2 个与元素相关。数组元素 External-NameS：内部名为 S(数字)的集合所对应的外部名。数组元素 Internal-NameL：外部名为 L(数字)的集合所对应的内部名。数组元素 Ri：给出元素 i 所属集合的内部名。（Find 指令可在 O(1)时间内完成 ）Nexti：给出与元素 i 同在一个集合中的下一个元素，
3、内容为 0 时，表示无下一元素（即元素 i 是该集合的最后一个元素） 。数组元素 ListS：给出内部名为 S 的集合中的第一个元素。数组元素 SizeS：给出内部名为 S 的集合中的元素个数。1.AInternal-NameI; /*将集合外部名 I,J 转为内部名 A 和 B*/2.BInternal-NameJ;3.wlg assume SizeA SizeB /*A 为小集合，B 为大集合*/ 4. otherwise interchange roles of A and B in5. ELEMENTListA; /*找出集合 A 的第一个元素*/6. while ELEMENT 0
4、do /*不断把 A 中*/*元素所在的集合名改为 B，直到全部改完为止*/7. RELEMENTB; /*改名*/8. LASTELEMENT; /*记下当前元素*/9. ELEMENTNextELEMENT; /*更新当前元素，准备执行下一轮*/*循环结束时，*/*LAST 中记录了原集合 A 中的最后一个元素*/10. NextLASTListB; /*置该元素的下一个元素为原 B 中的第一个元素，*/*从而实现 A 和 B 的合并*/11. ListBListA; /*置合并后的首元素为原 A 中的首元素*/12. SizeB SizeA + SizeB; /*置集合大小为 A、B 两
5、集合的规模之和*/13. Internal-NameKB;/*建立新集合的内部名与外部名的对应关系*/14. External-NameBK Union 算法除 6-9 行以外，其余均为常数时间。在最坏情况下，即当 A 和 B 的规模均为 n/2 时，6-9 行要执行 n/2 次, 以完成其中一个集合的元素所属集改名。即最坏情况下执行 1 次 Union 需要的时间为(n)。在最坏情况下，执行 n-1 次 Union 需要的时间是否为(n 2)？对 6-9 行进行总体分析，即考虑执行 n-1 次 Union 需要的总时间。每次总是小集合中的元素所属集合改名，每执行一次 Union，被改名元素所
6、在集合的规模至少扩大一倍。考虑任意一个元素 i 能够被改名的次数：初始时 i 所在集合只有一个元素，改名一次以后，i 所在集合的元素至少有 2 个，再改名一次以后，i 所在集合的元素至少有 4 个，故当 i 改名 k 次后，i 所在集合的元素至少有 2k 个，而 2k n 是必须满足的，故有 k Log2n，即任一元素 i 最多被改名 Log2n 次（i=1,2, ,n） 。故 n 个元素的改名总次数不会超过 n*Log2n，即在 n-1 次 Union 中，6-9 行执行改名的次数不超过(n logn)。在最坏情况下，改名总次数是可能达到(n logn)的：E.g. 设 n=2k, 先把单元
7、素集两两合并为双元素集；再把双元素集两两合并为 4 元素集；最后把两个 n/2 元素集合并为一个总的 n 元素集。在上述每一轮，需要改名的元素恰好为 n/2 个，共执行 k=Log2n 轮，故改名的总次数为 1/2*nLog2n。说明：若没有内部名，则每次合并时两个集合中的所有元素均要改名（改为 K） ，这样，在 n-1 次 Union 中改名的次数就会大大超过上述方式。另外，如果合并时不进行外部命名，即用 Union(I,J)的形式，则不需要另外再建立内部名，合并时仍然是小集合中的元素改名。总的开销比上述算法少一些， （减少得很有限）但对某些需要外部命名的应用就无法处理。 （参见后述）作业：设计一个数据结构，并给出一个算法的思路，能够较快地完成(n) 条 Union 和 (n)条 Find 指令；分析你所给的算法的时间复杂度。
