各位大大好,關於disjoint set以link list的形式,在weighted-union的方式下做
"a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAK
E-SET operations"
的時間複雜度,小弟有個問題想請教
附圖是cormen書談到這個的部分
https://i.imgur.com/G5VRkN0.jpg
https://i.imgur.com/QbszVe4.jpg
我對Theorem 21.1的理解是有m個operation,
其中有n個是Make-Set,
所以有n-1個是Union,有m-2n+1個是Find-Set
求這m個operation的總時間複雜度
證明所有Union的時間複雜度為nlog(n)的部分我很困惑,
我對書上寫的理解是,
在形成一個有n個元素集合的過程中,
每個元素最多被處理log(n)次,
所以總共最多需要nlog(n)次的時間
我的困惑點在於,
不是只要一個一個依序接起來總共接n-1次就好了嗎[email protected]@
就算是要生出n的元素,把他們都接上另一個已經存在的集合
最多也就接n次而已
為甚麼要用這種迂迴的方式推出一個好像不是tight bound的結果呢?
我覺得可能無論是theorem本身或證明我的理解都有問題
但我看了好幾遍還是覺得他是這個意思
還請各位強者們不吝指教, 非常感謝!!
對了, 文章是在cormen p566, p567