问题8： 为什么weighted-union 能降低操作平均代价？ Always append the shorter list onto the longer one
Always append the shorter list onto the longer one
Theorem 21.1 Using the linked-list representation of disjoint sets and the weighted-union heuris- tic,a sequence of m MAKE-SET,UNION,and FIND-SET operations,n of which are MAKE-SET operations,takes O(m +nlg n)time. 问题9： 你能否说出此定理证明 最核心的思想？
Proof Because each UNION operation unites two disjoint sets,we perform at most n-1 UNION operations over all.We now bound the total time taken by these UNION operations.We start by determining,for each object,an upper bound on the number of times the object's pointer back to its set object is updated.Consider a particular object x.We know that each time x's pointer was updated,x must have started in the smaller set.The first time x's pointer was updated,therefore,the resulting set must have had at least 2 members.Similarly,the next time x's pointer was updated,the resulting set must have had at least 4 members.Continuing on, we observe that for any k <n,after x's pointer has been updated [lgk]times, the resulting set must have at least k members.Since the largest set has at most n members,each object's pointer is updated at most [lg n]times over all the UNION operations.Thus the total time spent updating object pointers over all UNION operations is O(n Ig n).We must also account for updating the tail pointers and the list lengths,which take only (1)time per UNION operation.The total time spent in all UNION operations is thus O(n Ig n). The time for the entire sequence of m operations follows easily.Each MAKE- SET and FIND-SET operation takes O(1)time,and there are O(m)of them.The total time for the entire sequence is thus O(m +n lg n)