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)

總結

以上是生活随笔為你收集整理的算法导论第三版 21.2-3习题答案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。