21.2-4 對于圖21-3中操作序列的運行時間，給出其緊確的漸近界。假定采用的是鏈表表示和加權合并啟發式策略。

　　解：make-set，O(n)；加權合并啟發，每次將較短鏈表鏈接到較長鏈表，即每次將長度為1的集合鏈接到另外的鏈表上，時間O(n)。總時間O(n)。

21.2-5 當采用鏈表表示時，給出對UNION的一個簡單的改動，使得無需讓tail指針指向每個鏈表中的最后一個對象。無論是否采用了加權合并啟發式策略，你所做的修改不應改變UNION過程的漸進運行時間。

　　解：設合并的鏈表為A, B，將B鏈接到A上。可以將A的第一個元素指向下一個元素的指針指向head[B]，然后遍歷B，更改B中元素指向鏈表第一個元素的指針。然后將B中最后一個元素的指向下一個元素的指針指向A中的第二個元素。

?

21.3-4 證明：在采用了按秩合并和路徑壓縮時，任意一個包含m個MAKE-SET， FIND-SET，LINK的操作序列(其中所有的LINK操作出現在FIND-SET操作之前)需要O(m)的時間。在同樣情況下，如果僅用路徑壓縮啟發式呢？

　　解：采用記賬法：對每個MAKE-SET(x)操作收取2元費用，1元用來支付MAKE-SET(x)操作，另外1元用來支付x出現在FIND-SET的路徑上，并成為根節點的孩子的操作。FIND-SET(x)操作收取1元費用，LINK操作收取1元費用。這樣m個操作的需要O(m)時間，其中并未用來按秩合并策略，故僅用路徑壓縮啟發式所需的時間也為O(m)。

?

21-1 脫機最小值

　　解：a) 4 3 2 6 8 1

? ? ? ? ? ? ? b) 略

　　 ? ? ? c) 使用不相交集合數據結構，并將所有合法的集合k_j 按照j的順序用單個鏈表相連。OFF-LINE-MINIMUM(m,n)第二行相當于find-set(i)，第6行相當于在鏈表中合并兩個相鄰元素并執行union操作。每個操作的次數不超過n。又m = O(n)，所以最壞情況下時間復雜度為O(mα(n))。

轉載于:https://www.cnblogs.com/meteorgan/archive/2012/05/15/2499651.html

總結

以上是生活随笔為你收集整理的算法导论-用于不相交集合的数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

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