算法导论第三版 21.2-3习题答案

21.2-3
分析
要想做这道题，要先弄懂定理21.1的证明过程。
前提;加权合并启发式策略中的UNION()只需要进行指针的更新就可以实现合并操作(重点理解)
（1）首先明确UNION()操作的最多执行n-1次（注意：是次数）。因为MAKE-SET（）操作执行了n次，创造了n个对象。
（2）加权合并启发式策略是将较短的表拼接到较长的表中，而不是像图21-3所示的简单合并（简单合并就是{A}和{B}合并，然后{A,B}和{C}合并，然后{A,B,C}和{D}合并…依次合并下去）
（3）原文证明中有这一句话“因此第一次x的指针被更新时，结果集中一定至少有2个成员。类似地，下次x的指针被更新时结果集一定至少有4个成员”。第一次更新后结果集至少有2个成员很好理解，因为至少两个单独的对象才能进行合并操作；但是为啥说：下次x指针被更新后结果集至少有4个成员呢？因为不是简单合并操作，而是将较短的表连接到较长的表上，所以下一次x指针更新后结果集至少有：2+2=4个成员；类似的，再下一次x指针更新后结果集中至少有：4+4=8个成员。（自己多想想）
（4）理解了第（3）步就很好理解，当k<n时，x被更新了lg k（取上）次后，结果集至少有k个成员。从而可以推出：原文中的话“因为最大集合至多包含n个成员，故每个对象的指针在所有的UNION()操作中最多被更新lg n(取上)次”（注意：是每个对象的指针被更新的次数为：lg n(取上)次）
（5）因为有n个对象加上结合（4）中描述可以知道，所有UNION()操作中被更新的的对象指针的总次数是O(n * lg n)（注意：是指针被更新的总次数）
（6）因为加权合并启发式策略中的UNION()只需要进行指针的更新就可以实现合并操作，而一个指针更新的时间代价是:O(1)。所以UNION()操作的总的时间代价是O(1*(n*lg n))
(7)加上整个m个操作的序列，所以整个序列的总时间是O(m+n lg n)

答案：
对定理21.1的证明进行改造如下所示，使得该证明能表述摊还代价的概念。
证明：假设每次对指针的更新和查询操作的实际代价为1，我们为其支付的代价为2
（1）对于MAKE-SET操作：创造一个对象(即更新一个指针)的信用为：2-1=1。在执行了n次MAKE-SET操作后剩余的信用为：n；所以MAKE-SET的摊还代价上界为O(n/n)=O(1)
(2)对于FIND-SET操作：查找一个对象的信用为：2-1=1。在执行了x（假设执行了x次，且x<m）FIND-SET操作的信用为：x；所以FIND-SET的摊还代价上界为：O(x/x)=O(1）
（3）对于UNION操作：在所有的UNION操作中，一个对象指针需要更新至多lg n 次，所以在所有的UNION中一个对象指针的信用为：lg n * (2-1)=lg n；而因为有n个对象，所以在所有的UNION中指针更新后的信用为：n * lg n=nlg n.
在每个UNION操作中需要进行指针的查询，所以一次UNION操作中查询指针的信用为：2-1=1；
而由（1）知道，需要进行至多n-1次合并操作，所以所有的UNION操作中查询指针的信用为：(n-1) * 1=n-1
最后，计算UNION的摊还代价：O( [(nlg n)+(n-1)]/(n-1))=O(lg n)